March 2016
 

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/March2016.html[/url]

[QUOTE=Xyzzy;427927][url]https://www.research.ibm.com/haifa/ponderthis/challenges/March2016.html[/url][/QUOTE]

I haven't narrowed it enough to do anything useful with the question.

Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
[CODE]
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587[/CODE]
There were none for n=13. I haven't looked for patterns with even number of digits.

[QUOTE=axn;427940]Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
[CODE]
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587[/CODE]
There were none for n=13. I haven't looked for patterns with even number of digits.[/QUOTE]

the patterns I see that should hold regardless of length are related to the first n must be the end of a square reversed and the rest must match up to give those digits ( so the last has to be a number mod 10 that allows a square to end in the first digit hence the 1 and 0 combination (9^2)%10==1)

From Ibm Ponder This:

Update (07/03):
A solution with more than 20 digits will earn you a '**'.

[QUOTE=axn;427940]Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
[CODE]
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587[/CODE]There were none for n=13. I haven't looked for patterns with even number of digits.[/QUOTE]
n=8 90899553
:razz:

Found the two n=15s

n=1 1
n=1 5
n=1 6
n=3 963
n=4 9,867
n=5 65,766
n=5 69,714
n=7 6,317,056
n=8 90,899,553
n=9 169,605,719
n=10 4,270,981,082
n=11 96,528,287,587
n=12 465,454,256,742
n=12 692,153,612,536

They seem to be getting rarer. Has anyone a clue of how many we should expect to find of a certain size?
Running a search upto 18 digits. This should take a while. 20 digits is out of my reach so far.

Is there an [B]elegant[/B] way to solve this problem or is writing a program and cycling through candidates the only way to go?

Sometimes it is difficult to tell when brute-force is actually the intended solution method. I started playing around with a few examples (and even built a grammar-school 15-digit by 15-digit multiplication problem to build up the product line-by-line in Excel) but things get unwieldy fairly quickly. As in GIMPS, knowing the position and size of potential carries becomes vital...but there is no easy way to really do this here.

[QUOTE=NBtarheel_33;428924]Is there an [B]elegant[/B] way to solve this problem or is writing a program and cycling through candidates the only way to go?

Sometimes it is difficult to tell when brute-force is actually the intended solution method. I started playing around with a few examples (and even built a grammar-school 15-digit by 15-digit multiplication problem to build up the product line-by-line in Excel) but things get unwieldy fairly quickly. As in GIMPS, knowing the position and size of potential carries becomes vital...but there is no easy way to really do this here.[/QUOTE]

[SPOILER]Quadratic residues reduce the candidate pool massively. I will explain my method in full once the deadline is up. Found an 18 digit one last night.
I think I may have hit on the way to get to 20 digits today. The squaring was the slowest bit for me. I should be able to go from one square to another though. n^2-(n-x)^2=2*x*n-x^2 which is much easier to calculate and add than do another square.[/SPOILER]

Some supermod should put your post in SPOILER ALERT.
You actually disclosed the method... :razz:

Are there no 14 & 18 digit answer to this? My program didn't turn-up anything. I am having doubt whether I am doing it right or not.

Though it did reproduce the 10 & 12 digit ones posted above. My code is for even digits only.

[QUOTE=ramshanker;429261]Are there no 14 & 18 digit answer to this? My program didn't turn-up anything. I am having doubt whether I am doing it right or not.

Though it did reproduce the 10 & 12 digit ones posted above. My code is for even digits only.[/QUOTE]

There is an 18 digit solution.

[QUOTE=henryzz;429419]There is an 18 digit solution.[/QUOTE]

Ok, I figured out the bug in my python code. Can someone explain this to me.

After a certain number of digits, python results give incorrect division values.

[COLOR="Red"]>>> int( 194216878433174216 / 10 ) % 10
0[/COLOR]
[COLOR="SeaGreen"]>>> int( 19421687843317421 / 10 ) % 10
2
>>> int( 1942168784331742 / 10 ) % 10
4
>>> int( 19421687843317 / 10 ) % 10
1
>>> int( 1942168784331 / 10 ) % 10
3
>>> int( 194216878433 / 10 ) % 10
3[/COLOR]


First result is wrong. Trying on my 64 bit Python 3.5.0 shell. Is it a bug in python interpreter or it's supposed to be this way only?
It gives correct for high digit multiplication.

>>> 194216878433174216 * 194216878433174216
37720195868326371910875197407214656

So obviously it can handle >64 bit numbers, but some problem at the boundary?

Anyway I figured out a way for odd number and found both 15 digit ones. Now running for those 18 digit ones. :)

[QUOTE=ramshanker;429503]Ok, I figured out the bug in my python code. Can someone explain this to me.

After a certain number of digits, python results give incorrect division values.

[COLOR="Red"]>>> int( 194216878433174216 / 10 ) % 10
0[/COLOR]
[COLOR="SeaGreen"]>>> int( 19421687843317421 / 10 ) % 10
2
>>> int( 1942168784331742 / 10 ) % 10
4
>>> int( 19421687843317 / 10 ) % 10
1
>>> int( 1942168784331 / 10 ) % 10
3
>>> int( 194216878433 / 10 ) % 10
3[/COLOR]


First result is wrong. Trying on my 64 bit Python 3.5.0 shell. Is it a bug in python interpreter or it's supposed to be this way only?
It gives correct for high digit multiplication.

>>> 194216878433174216 * 194216878433174216
37720195868326371910875197407214656

So obviously it can handle >64 bit numbers, but some problem at the boundary?

Anyway I figured out a way for odd number and found both 15 digit ones. Now running for those 18 digit ones. :)[/QUOTE]

The [c]/[/c] operator always gives a floating point result (in Python 3+). The result highlighted is the first number on your list large enough that the last digit of the result is lost due to rounding error. Use the [c]//[/c] operator instead (and drop the [c]int()[/c] conversion).

[code]In [1]: 194216878433174216/10
Out[1]: 1.942168784331742e+16

In [2]: 19421687843317421/10
Out[2]: 1942168784331742.0

In [3]: 194216878433174216//10
Out[3]: 19421687843317421[/code]

Ok, found the 18 digit one. :banana:

Run-time 5967.29 sec.

Time to go for the big gun... any hint how many minimum digits for "**"? :grin:

If my program did not miss any solutions, then there are 2 solutions with 21 digits. There seem to be no solutions with 19 or 20 or 22 digits.

[QUOTE=ramshanker;429534]Ok, found the 18 digit one. :banana:

Run-time 5967.29 sec.

Time to go for the big gun... any hint how many minimum digits for "**"? :grin:[/QUOTE]

That is much faster than mine. Mine took a couple days.

[QUOTE=Anonuser;429536] there are 2 solutions with 21 digits. .[/QUOTE]

1 Found.... yeaaaaaaaaaa :showoff: . Let's see how much higher I can go.

The official solution (what is essentially my solution :smile:) is out at: [url]https://www.research.ibm.com/haifa/ponderthis/solutions/March2016.html[/url]
I've updated the corresponding oeis sequence.

[QUOTE=axn;427940]Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
[/QUOTE]
[QUOTE=ramshanker;429534]Ok, found the 18 digit one. :banana:
Run-time 5967.29 sec.[/QUOTE] etc. (other posts)

My timings in the low range: for
n value, timing in thread time on my ancient core-i3
n=15: <1 second
n=18: 2 seconds [to get *]
n=21: 61 seconds (close to the famous 1 minute rule) [to get **]
n<=30: 152 hours

[QUOTE=R. Gerbicz;430729]The official solution (what is essentially my solution :smile:) is out at: [url]https://www.research.ibm.com/haifa/ponderthis/solutions/March2016.html[/url]
[/QUOTE]

So we can send a write-up also about the solution? This is my first time participating in Ponder-This contest. I just mailed them the number from my O(10^(d/2)) implementation output.

I wrote mine in python, an interpreted language, so I guess (wild guess) I could achieve at least 5 times improvement in run time with C code. However lost my interest after that lucky (early in the search sequence) 21 digit solution. My Python code managed ~140k candidate numbers per second.

[QUOTE=ramshanker;430732]So we can send a write-up also about the solution?[/QUOTE]

Yes, of course. Here I'm regularly posting solutions of the month puzzle (if I've solved).

[QUOTE=ramshanker;430732]I wrote mine in python, an interpreted language, so I guess (wild guess) I could achieve at least 5 times improvement in run time with C code. However lost my interest after that lucky (early in the search sequence) 21 digit solution. My Python code managed ~140k candidate numbers per second.[/QUOTE]

In general Python is not that slow. And it is a little technique to avoid the somewhat costly squaring in most of the cases (my solution was in c).

The next term is a(28)=42438303108538316396992097393368 found by Dieter Beckerle using my posted algorithm, but his own code. And there is no more term up to 10^32. The oeis sequence is updated, now it is in draft. ([url]https://oeis.org/A269588[/url]).

ps. Note that here still k=3, so there is a speedup of 1000 over the classical approach.