138 - Street Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

Problem 138

Post by Charlla » Thu Dec 04, 2003 12:26 am

Hy!


There are a relantionship between [6 , 8] and [35, 49]
? I tried to find but I didn't get it.

If I find it, I will generate the other numbers in a easy way.



Thanks,

Charla :roll:

Nikolay Archak
New poster
Posts: 6
Joined: Tue Dec 02, 2003 6:43 am
Contact:

Post by Nikolay Archak » Thu Dec 04, 2003 1:07 am

Hi!

I can give you a hint if you want.
You should find first 10 pairs of numbers n, m with a property
that 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m

For example, 1 + ... + 5 = 7 + 8 = 15.

Here, n corresponds to the programmer house number and m to the maximum house number on this street.

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

Problem 138 - Pell's Formula

Post by Charlla » Fri Dec 05, 2003 3:41 am

Hy!

How can I generate the next pair of numbers using the Pell's Formula
(if it is possible, of course.)?

Thanks,

Charlla :roll:

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Dec 05, 2003 11:19 am

Just write on a paper first 6 numbers found by brute force and try to find relation between them.
_____________
NO sigNature

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Dec 06, 2003 7:43 am

i have found the numbers but yet can't get any relation. plz help.
"Everything should be made simple, but not always simpler"

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

138 - Understanding

Post by Charlla » Fri Dec 19, 2003 5:08 am

Hy!

I understood the relation 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m
that you said. But, how can I "guess" that after 6, the next number should
be 35?

Thanks,

Charlla :roll:
==========
Nikolay Archak wrote:Hi!

I can give you a hint if you want.
You should find first 10 pairs of numbers n, m with a property
that 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m

For example, 1 + ... + 5 = 7 + 8 = 15.

Here, n corresponds to the programmer house number and m to the maximum house number on this street.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Dec 19, 2003 6:50 am

you'll have to spot the pattern.

There is a 2 parameter recursion I know that works, but I dunno why.

Furthermore, you can look into pell's equation, you can transform the problem into pell's equation and use the algorithm for pell to do it. you can google pell, I do not familiar with the details.

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

Problem 138 - Pell's Equation

Post by Charlla » Sun Dec 21, 2003 4:11 pm

Hy!

Thanks a lot. I'll try.

Charlla :D
----------

yiuyuho wrote:you'll have to spot the pattern.

There is a 2 parameter recursion I know that works, but I dunno why.

Furthermore, you can look into pell's equation, you can transform the problem into pell's equation and use the algorithm for pell to do it. you can google pell, I do not familiar with the details.

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Thu Jan 29, 2004 8:03 pm

Hi all,

In case you're not sure whether your solution is correct, or just plain want to know some examples, here are the first 12 solutions.
I have omitted solution 10 to prevent people from simply sending in this list.

Code: Select all

         6          8
        35         49
       204        288
      1189       1681
      6930       9800
     40391      57121
    235416     332928
   1372105    1940449
   7997214   11309768
  ........   ........
 271669860  384199200
1583407981 2239277041

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

138 - Steet numbers

Post by Rav » Mon Mar 08, 2004 7:57 pm

I need help from people's whos have linux and same compiler like OJ. plz write output for this program, becouse i get that output on my win98 with devc++(orginal compiler):
[output removed]
And there is code:

Code: Select all

code removed by Jan
Best Regards Rav
Rafał Sokołowski

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Mon Mar 08, 2004 8:27 pm

Your answer is correct. I compared them with my AC code.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

Post by Rav » Mon Mar 08, 2004 11:25 pm

Yes i know that :). but try send this to OJ, in 0,004s is WA.
Rafał Sokołowski

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Re: 138 - Steet numbers

Post by junbin » Tue Mar 09, 2004 2:11 am

Rav wrote:I need help from people's whos have linux and same compiler like OJ. plz write output for this program, becouse i get that output on my win98 with devc++(orginal compiler):
[output removed]
And there is code:

Code: Select all

code removed by Jan
Best Regards Rav
I think you need long long.. not long int

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

138 the Math way.

Post by _.B._ » Mon Apr 05, 2004 8:39 am

Greetings!.
What's the Math way to do this problem?.
I work with Pascal, and I made it adding and testing, but it takes so much time (even with (a+b)*(b-a+1)/2 will take too long).
What formulas can be used?.
Thanks in advance.
_.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Re: 138 the Math way.

Post by junbin » Tue Apr 06, 2004 3:22 am

_.B._ wrote:Greetings!.
What's the Math way to do this problem?.
I work with Pascal, and I made it adding and testing, but it takes so much time (even with (a+b)*(b-a+1)/2 will take too long).
What formulas can be used?.
Thanks in advance.
I think the maths formula is already posted somewhere on this forum.. just do a search for it. Alternatively, go to the main page (acm.uva.es/problemset) and then scroll to the bottom. Visit Steven Halim's website. The answer is on there somewhere as well.

Post Reply

Return to “Volume 1 (100-199)”