March 2016

[henryzz]

Originally Posted by ramshanker

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.

There is an 18 digit solution.

[ramshanker]

Originally Posted by henryzz

There is an 18 digit solution.

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.

>>> int( 194216878433174216 / 10 ) % 10
0
>>> 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


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. :)

[Dubslow]

Originally Posted by ramshanker

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.

>>> int( 194216878433174216 / 10 ) % 10
0
>>> 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


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. :)

The / 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 // operator instead (and drop the int() conversion).

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

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

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

[ramshanker]

Ok, found the 18 digit one.

Run-time 5967.29 sec.

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

[Anonuser]

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.

[henryzz]

Originally Posted by ramshanker

Ok, found the 18 digit one.

Run-time 5967.29 sec.

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

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

[ramshanker]

Originally Posted by Anonuser

there are 2 solutions with 21 digits. .

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

[R. Gerbicz]

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

Originally Posted by axn

Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.

Originally Posted by ramshanker

Ok, found the 18 digit one.
Run-time 5967.29 sec.

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

[ramshanker]

Originally Posted by R. Gerbicz

The official solution (what is essentially my solution ) is out at: https://www.research.ibm.com/haifa/p...March2016.html

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.

[R. Gerbicz]

Originally Posted by ramshanker

So we can send a write-up also about the solution?

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

Originally Posted by ramshanker

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.

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).

[R. Gerbicz]

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. (https://oeis.org/A269588).

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