138 - Street Numbers

[Charlla]

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

[Nikolay Archak]

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]

Hy!

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

Thanks,

Charlla

[Farid Ahmadov]

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

[anupam]

i have found the numbers but yet can't get any relation. plz help.

[Charlla]

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
==========

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]

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]

Hy!

Thanks a lot. I'll try.

Charlla
----------

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]

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]

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

[Raiyan Kamal]

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

[Rav]

Yes i know that . but try send this to OJ, in 0,004s is WA.

[junbin]

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

[_.B._]

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]

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.