hacker.org

The given answer is 3432948736, but I think the true answer should be 3432948733.

(It's found by tog. When I told him I was in trouble, he said: "Try submitting your answer+3." Great guess!)

tails wrote:The given answer is 3432948736, but I think the true answer should be 3432948733.

(It's found by tog. When I told him I was in trouble, he said: "Try submitting your answer+3." Great guess!)

Yes, of course, you are right. What a flaw! @adum: Could you correct it, please.

cool, fixed

Thanks.

BTW: The solution can be derived from http://www.research.att.com/~njas/sequences/A121319 if one subtracts 3...

teebee wrote:Thanks.

BTW: The solution can be derived from http://www.research.att.com/~njas/sequences/A121319 if one subtracts 3...

I did it with modular exponentiation as described in http://mathforum.org/library/drmath/view/51625.html, using some online tool like http://banach.millersville.edu/~bob/mat ... ation.html

Wow, ok. My first initial guess was correct. I solved the iterative equations up to ack(3,x) and then wrote ack(4,x) to be calculated iteratively from ack(3, ack(4,x-1)).

Still dont really understand how mod works with power of powers and how to prove my answer, it was just the answer that was repeated in ack( 4, >=9 ).

Ahh, the links from tog helped explained how to solve the tower of powers modulus

This was my way to the solution (knowing that the solution must be 2^2^..... - 3 MOD 10^10):

First I found that the last 10 digits of 2^7812510 = 0000001024, so
2^x has the same last 10 digits as 2^(x MOD 7812500) for large x.

7812500 is 2^2 * 5^9. Then I looked at 2^x MOD 7812500 and found that
it's the same as 2^(x MOD 1562500) MOD 7812500, where 1562500 = 2^2 * 5^8.

After going down to 2^2 * 5^0, I started with 2^2^... = 0 MOD 4 and so... So basically it's modular exponentiation too.

The following Python-Code instantly prints out the answer:

efe wrote:The following Python-Code instantly prints out the answer:

Code: Select all

x,p = 0,1
while p!=x:
	p,x = x,pow(2,x,10**10)
print x-3

Wow, I didn't know that Python's pow is capable of modding. Nice!

Yes, pow-with-mod is nice and efficient.

I think this challenge loses something because the base still has a factor of 2. "Compute the last 7 digits of ack(7,7) in base 7" would foil efe's code and MerrickOWA's observation, I think, but I could be wrong.

7 is a bit low though - maybe 11 or 13 would be better, or 9 - I guess it doesn't need to be prime, just odd.

Actually, I think maybe you should put up two more variants - the last-7-digits-in-base-7, and something much larger, e.g. last-49-digits-in-base-49. Base 7 is pretty easy, but by not having a factor of 2 it does break some of the methods described here. Bigger bases like 49 are still efficiently solvable but (I think) need more thought... or maybe I thought more than was necessary - it's hard to tell. At least my original solution leant on some brute force that works for single-digit bases but is too inefficient for bigger numbers, so I did have to work at it a bit more.

My new solution works fine even for three-digit numbers, so (assuming my solution is correct) it is possible to solve big numbers efficiently - i.e. about ten seconds on a 600MHz CPU with half a gig of RAM - if you have the right algorithms.

The trouble is, I don't have a good way to check the answers! For small values I can compute 2**2**2**... far enough to verify the result, but it quickly runs out of scope. efe's loop works for checking most even numbers, even if they're large, but they're kind of easy anyway, and it doesn't work for the harder odd numbers at all.

So it looks like there are no quick checks. Maybe it's worth adding these challenges anyway, though, and later if anybody disagrees about the answers then we can discuss it?

teebee wrote:BTW: The solution can be derived from http://www.research.att.com/~njas/sequences/A121319 if one subtracts 3...

Oh, the link has changed: http://oeis.org/A121319.

Yharaskrik wrote:This was my way to the solution (knowing that the solution must be 2^2^..... - 3 MOD 10^10):

First I found that the last 10 digits of 2^7812510 = 0000001024, so
2^x has the same last 10 digits as 2^(x MOD 7812500) for large x.

7812500 is 2^2 * 5^9. Then I looked at 2^x MOD 7812500 and found that
it's the same as 2^(x MOD 1562500) MOD 7812500, where 1562500 = 2^2 * 5^8.

After going down to 2^2 * 5^0, I started with 2^2^... = 0 MOD 4 and so...

Code: Select all

                      2^...%      4=                 =         4
=>                  2^2^...%     20=      2^4%     20=        16
=>                2^2^2^...%    100=     2^16%    100=        36
=>              2^2^2^2^...%    500=     2^36%    500=       236
=>            2^2^2^2^2^...%   2500=    2^236%   2500=      1236
=>          2^2^2^2^2^2^...%  12500=   2^1236%  12500=     11236
=>        2^2^2^2^2^2^2^...%  62500=  2^11236%  62500=     11236
=>      2^2^2^2^2^2^2^2^...% 312500=  2^11236% 312500=    136236
=>    2^2^2^2^2^2^2^2^2^...%1562500= 2^136236%1562500=    136236
=>  2^2^2^2^2^2^2^2^2^2^...%7812500= 2^136236%7812500=   3261236
=>2^2^2^2^2^2^2^2^2^2^2^...%  10^10=2^3261236%  10^10=3432948736

So basically it's modular exponentiation too.

I made several bugs when using this approach so I finally decided to use mod 10^10 exponentation till 2^x stabilises (of course -3).