 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I was going through some old stuff on my hard drive, and I came across a
small code snippet which led to a cute little problem:
I have a number which is defined with the following bit of pseudocode,
with all variables representing ideal mathematical integers:
n = 2
for(a = n; a > 0; a--)
for(b = n; b > 0; b--)
for(c = n; c > 0; c--)
for(d = n; n > 0; d--)
n++;
print n
What are the last 10 digits of the result printed by this program?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I just spotted a typo: The code should obviously read:
n = 2
for(a = n; a > 0; a--)
for(b = n; b > 0; b--)
for(c = n; c > 0; c--)
for(d = n; d > 0; d--)
n++;
print n
Since the version I gave didn't terminate!
Kevin Wampler wrote:
> I was going through some old stuff on my hard drive, and I came across a
> small code snippet which led to a cute little problem:
>
> I have a number which is defined with the following bit of pseudocode,
> with all variables representing ideal mathematical integers:
>
> n = 2
> for(a = n; a > 0; a--)
> for(b = n; b > 0; b--)
> for(c = n; c > 0; c--)
> for(d = n; n > 0; d--)
> n++;
> print n
>
> What are the last 10 digits of the result printed by this program?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> n = 2
> for(a = n; a > 0; a--)
> for(b = n; b > 0; b--)
> for(c = n; c > 0; c--)
> for(d = n; d > 0; d--)
> n++;
> print n
Damned mutable state! >_<
OK, well
for(d=n; d>0; d--) n++;
is equivilent to
n = 2*n;
so we have
for(c=n;c>0;c--) n = 2*n;
which is
n = n * 2^n;
so now we have
for(b=n;b>0;b--) n = n * 2^n;
Now there's trouble. You see, initially we have
n[0] = n
On the next iteration we have
n[1] = n[0] 2^n[0] = n 2^n
But then we have
n[2] = n[1] 2^n[1] = (n 2^n) 2^(n 2^n)
You can simplify this to
n[2] = n 2^(n + n 2^n)
but that's still quite complex. More to the point, on the next iteration
it'll get even more complex, and I don't see a closed-form solution to this.
More to the point, by the time a=1, n=2048. That means that the b-loop
runs 2048 times. And when you consider that 2048 * 2^2048 is
6618522843404494295186406745839606161498952226757731129780294743557
0493724401440549267868490798926773634494383968047143923956857140205
4064027405360874460838310520368482324399959044049927980075147183260
4341057037983087046378008526061944441720519919712375121070497035272
7833755425876102776028267313405809429548880554782040765277562828362
8842383254654485203483075749433459903099416426669267233797295981858
3473505473250041540988386836142315991377081221877271190177224955315
3402287759789517121744336755350465901655205184917370974202405586941
2110653955407655676631932971733672542303136122441829419995004023881
95450053080383488
(i.e., 6.618 * 10^619), you realise that the very next iteration is
going to produce some absurdly *huge* number. This explains why the
program I wrote eats several GB of RAM without ever coming up with an
answer.
The difficulty, then, is coming up with an algorithm to compute the
least-significant digits of λ n → n 2^n without computing the entire
number. I'll have to go check my number theory; I don't recall the exact
details of the algorithm.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> The difficulty, then, is coming up with an algorithm to compute the
> least-significant digits of λ n → n 2^n without computing the entire
> number. I'll have to go check my number theory; I don't recall the exact
> details of the algorithm.
You're asking for the last 10 digits of the answer. In other words, the
answer modulo 10^10. (Assuming you meant the last 10 *decimal* digits...)
In modular arithmetic,
(X mod M) * (Y mod M) = (X * Y) mod M
In other words, we can reduce our running total to the least positive
reside class mod 10^10 and still get the same answer. Handling
billion-digit numbers is quite expensive, but piffling 10-digit numbers
are no match for the GMP.
Unfortimately,
(X mod M)^(Y mod M) ≠ (X^Y) mod M
But fortunately,
(X mod M)^Y = (X^Y) mod M
due to the first theorum. Better still,
A+B = Y ⇒ (X mod M)^A * (X mod M)^B = (X^Y) mod M
by the usual first law of logarithms. This gives us the binary
exponentiation algorithm:
x = 1;
b = base;
e = exponent;
while (e>0)
if odd(e) then x = x*b mod m;
e = shift_right(e);
b = b*b mod m;
At any time, you need to deal with numbers containing at most 20 digits.
So what's the answer? I make it
.....1,549,498,368
It took about 0.2 seconds to compute. I have very little confidence that
this is correct though.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> .....1,549,498,368
I recognise those last 6 digits! I think I got them from my program, but
then my method was too slow to do any more digits in reasonable time.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> .....1,549,498,368
>
> I recognise those last 6 digits! I think I got them from my program,
> but then my method was too slow to do any more digits in reasonable time.
Heh. Could be just fluke.
I'm still not 100% certain that my program works. For example, the
exponent is reduced as per the modulus too, which could affect the
answer. As a quick check, I tried rerunning with 20 digits:
.......1,225,862,901,549,498,368
So the digits don't change by making the calculation wider. Which
presumably means it's wide enough not to screw up the answer. (Or it's a
very big fluke. You never know - mathematics is like that!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I'm still not 100% certain that my program works. For example, the
> exponent is reduced as per the modulus too, which could affect the
> answer. As a quick check, I tried rerunning with 20 digits:
>
> .......1,225,862,901,549,498,368
Next task, give us some indication of how big n is :-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> Next task, give us some indication of how big n is :-)
I can see I won't get much work done today...
OK, well we have
d = λ n → n 2
c = λ n → n 2^n
b = λ n → c@n n
a = λ n → b@n n
where "b@n" means "b applied n times".
If n = 100, then 2^n ≈ 10^30, while is a mere 10^2 times larger. As n
becomes larger, the difference becomes more and more insignificant. So,
we can approximate with
c = λ n → 2^n
On that bases, the final result is guaranteed to be an exact power of 2.
We just need to figure out which one.
Using Knuth's "up-arrow notation", we have
c = λ n → 2↑n
b = λ n → 2↑↑n
a = λ n → 2↑↑↑n
So the answer we seek is (approximately) 2↑↑↑2. In other words, the
pentation of 2 with 2. Unfortunately, I don't know of any efficient way
to compute the size of this ludicrously massive quantity.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> So the answer we seek is (approximately) 2↑↑↑2.
Isn't that 4?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> scott wrote:
>>> .....1,549,498,368
>>
>> I recognise those last 6 digits! I think I got them from my program,
>> but then my method was too slow to do any more digits in reasonable time.
>
> Heh. Could be just fluke.
Nah. That would be a one in a million chance.
Wait, no, one in a million chances work out all the time!
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> So what's the answer? I make it
>
> .....1,549,498,368
I believe that answer is correct, although I'm not sure your reasoning
behind the algorithm was watertight. In particular, since you're
applying modular exponentiation in each iteration, you're implicitly
assuming that a^b mod m == a^(b mod m) in the next iteration.
Fortunately this ends up bring very close to true in this case, so
everything still works out, but to be totally safe you should really
compute everything mod lcm(10^10,phi(10^10)) = 10^11. Unless I was
overly conservative in my analysis somewhere.
Now for a tricker question, say I add another loop:
n = 2
for(a = n; a > 0; a--)
for(b = n; b > 0; b--)
for(c = n; c > 0; c--)
for(d = n; d > 0; d--)
for(e = n; e > 0; e--)
n++
print n
What are the last five digits printed?
Note that I haven't actually worked through this yet to be sure that my
idea or solving it will actually work, so be forewarned that I'm not
positive it's possible.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> So the answer we seek is (approximately) 2↑↑↑2.
>
> Isn't that 4?
No, since 2^^^2 = 2^^2^^2 = 2^^(2^2^2) = 2^^16 =
2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2.
However, in this case you can very easily give a somewhat tighter lower
bound of 2^^2048, that is 2^2^2^2^ ... 2048 times ... ^2^2^2
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
>
> Now for a tricker question, say I add another loop:
>
> n = 2
> for(a = n; a > 0; a--)
> for(b = n; b > 0; b--)
> for(c = n; c > 0; c--)
> for(d = n; d > 0; d--)
> for(e = n; e > 0; e--)
> n++
> print n
>
> What are the last five digits printed?
>
Ok, I haven't been able to post today since I've been on airplanes on or
airports without wireless the whole time, but I implemented the solution
and it seems to work, so this problem is totally solvable, and only
takes a fraction of a second on my computer.
It turns out that the solution is actually quite simple too! Possibly
even more so than that to the last puzzle -- although certainly not as
mathematically concise.
Actually pretty fun, so feel free to give it a shot knowing that it does
indeed have a relatively simple solution!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>
> (Assuming you meant the last 10 *decimal* digits...)
>
Man, meaning the last ten binary digits would have made this the lamest
trick question ever (so yeah, you're correct in solving for decimal
obviously).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> .....1,549,498,368
>
> I recognise those last 6 digits! I think I got them from my program,
> but then my method was too slow to do any more digits in reasonable time.
>
It's interesting that you had an algorithm that could compute six digits
but not ten. You might try running it on the second version of the
puzzle that I gave, since I only ask for the last five digits in that
case. Maybe it'll work!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> So the answer we seek is (approximately) 2↑↑↑2.
>>
>> Isn't that 4?
>
> No, since 2^^^2 = 2^^2^^2
I understood from wikipedia that 2^^^3 = 2^^2^^2 and 2^^^2 = 2^^2. Is that
wrong?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> .....1,549,498,368
>>
>> I recognise those last 6 digits! I think I got them from my program, but
>> then my method was too slow to do any more digits in reasonable time.
>>
>
> It's interesting that you had an algorithm that could compute six digits
> but not ten.
Well I simplified as far as Invisible did, and then didn't go through the
modular math to simplifiy it, just applied the mod operator at various
points in the code. Using mod 1e5 took a fraction of a second, mod 1e6 took
about 10 seconds, and mod 1e7 never finished!
> You might try running it on the second version of the puzzle that I gave,
> since I only ask for the last five digits in that case. Maybe it'll work!
Hmmm.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Ok, I haven't been able to post today since I've been on airplanes on or
> airports without wireless the whole time, but I implemented the solution
> and it seems to work, so this problem is totally solvable, and only
> takes a fraction of a second on my computer.
>
> It turns out that the solution is actually quite simple too! Possibly
> even more so than that to the last puzzle -- although certainly not as
> mathematically concise.
>
> Actually pretty fun, so feel free to give it a shot knowing that it does
> indeed have a relatively simple solution!
I have a truly marvelous proof of this, which this forum is too small to
contain...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/07/2010 8:56 AM, Invisible wrote:
> Kevin Wampler wrote:
>
>> Ok, I haven't been able to post today since I've been on airplanes on
>> or airports without wireless the whole time, but I implemented the
>> solution and it seems to work, so this problem is totally solvable,
>> and only takes a fraction of a second on my computer.
>>
>> It turns out that the solution is actually quite simple too! Possibly
>> even more so than that to the last puzzle -- although certainly not as
>> mathematically concise.
>>
>> Actually pretty fun, so feel free to give it a shot knowing that it
>> does indeed have a relatively simple solution!
>
> I have a truly marvelous proof of this, which this forum is too small to
> contain...
LOL ;-)
--
Best Regards,
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I have a truly marvelous proof of this, which this forum is too small to
>> contain...
>
> LOL ;-)
You may laugh, but for 300 years mathematicians have been unable to
rediscover this "marvellous proof" - so excuse me if mathematicians are
a teeny bit skeptical about sweeping claims. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>
> I understood from wikipedia that 2^^^3 = 2^^2^^2 and 2^^^2 = 2^^2. Is
> that wrong?
>
Nope, it appears that the error was all mine. Sorry about that!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>
> I have a truly marvelous proof of this, which this forum is too small to
> contain...
LOL. Fortunately the code is small enough to post, I just didn't want
to spoil the puzzle.
If you want to check your algorithm, the last five digits of the case
with ten nested for-loops I get as being 68608.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I sent the problem to someone on IRC, who spent a while trying to solve it,
then he posted it to ycombinator:
http://news.ycombinator.com/item?id=1480303
Interesting comments there.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> I sent the problem to someone on IRC, who spent a while trying to solve it,
> then he posted it to ycombinator:
>
> http://news.ycombinator.com/item?id=1480303
>
> Interesting comments there.
>
Cool! I'm glad to see that people like it!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
>
> Now for a tricker question, say I add another loop:
>
> n = 2
> for(a = n; a > 0; a--)
> for(b = n; b > 0; b--)
> for(c = n; c > 0; c--)
> for(d = n; d > 0; d--)
> for(e = n; e > 0; e--)
> n++
> print n
>
> What are the last five digits printed?
>
Don't read if you don't want the puzzle spoiled for you.
Ok, since nobody's posted in a while I'll assume that either everyone's
lost interest or they're ready to hear the solution. Invisible had the
right answer (minus some minor analysis issues) for the case with four
loops, but the technique he used doesn't extend well beyond that.
To figure out how to make things work for more nested for-loops, let's
consider the function representing the body of the innermost loop:
f_0(n) = n+1
On successive iterations of the innermost loop, we end up computing:
f_0(n)
f_0(f_0(n))
f_0(f_0(f_0(n)))
etc...
Of course, we're only interested in the last k digits of the answer, so
the values of these successive iterations end up repeating. Obviously
it's easy to represent this in closed from, but let's say we don't want
to do that. Then we can explicitly represent this with:
orbit_0 = []|[2,3,4,...,10^k,0,1]
The notation A|B here indicates that the initial value of n (2 in this
case) goes through the values in A once, and then loops through the
values in B forever. We'll call this the orbit of n mod 10^k under f_0,
meaning that these are the values we get if we start at n and then keep
applying f_0. For convienence I'll call A and B the prefix and loop of
the orbit respectively.
The method of solving the puzzle for many nested loops will involve
computing orbit_i, which is the orbit of n mod 10^k under f_i, where f_i
is the function defined by i nested for-loops. The a'th element in this
orbit will be given by f_i^a(n), which stands for a compositions of f_i,
so f_i^3(n) = f_i(f_i(f_i(n))).
In this approach to solving the problem, we'll store each orbit_i
explicitly. Thus we can get the value of f_i^a(n) by simply indexing
into orbit_i. In the case that the orbit's prefix is empty, then we can
do this by f_0^a(n) = orbit_i.loop[ (indexOf(n,orbit_i) + a) mod
period(orbit_i) ], which we'll write as orbit_i[n,a] for shorthand. If
the or orbit's prefix is non-empty, then the formula is a bit more
complicated, but still not too bad, and we'll denote it with
orbit_i[n,a] in any case.
So far this may not seem very interesting, but the power of this way of
looking at things will become apparent if we consider the function
defined by having a single for-loop:
for(a = n; a > 0; a--)
n = f_{i-1}(n)
As noted before, this loop defines the function:
f_i(n) = f_{i-1}^n(n)
Now, the trick to getting this whole approach to work is to directly
calculate orbit_i entirely in terms of the initial value of n (2 in this
case) and orbit_{i-1}. Since we show that the first element in orbit_i
(it's 2), it's sufficient to be able to calculate element a in orbit_i
given element a-1. It's pretty direct to see how to do this:
Since: orbit_{i-1}[n,a] = f_{i-1}^a(n)
and: f_i(n) = f_{i-1}^n(n)
then: f_i(n) = orbit_{i-1}[n,n]
So to generate the orbit defined by f_i, we can use the procedure:
f_i^0(n) = 2
f_i^a(n) = orbit_{i-1}[f_i^{a-1}(n), f_i^{a-1}(n)]
= orbit_i[n,a]
This allows us to generate values of f_i^a(n) until we hit a repeated
value, at which point we have the full definition of orbit_i. Thus if
we want the last m digits of the result if we start at n and use i
nested loops, we just look up the value of orbit_i[n,n]. Thus the
algorithm requires linear time in the numeber of nested loops, although
exponential time in the number of digits you want to return (which is
why I changed the problem to only ask for five digits).
The Python code I udes to solve this problem (posted below) uses this
procedure to get the answer for the case with five nested for-loops: 86528
Even better, the Python code allows you to create an orbit of orbits,
and thus find that the last five digits for the case with 10^100 nested
for-loops are 45728! Not bad considering how completely intractable the
problem appears at first. I also think it's sort of nifty that the
entire algorithm is basically just fancy array indexing, so in some
sense it's quite simple. Also, I haven't quite proved rigorusly that
this algorithm works, and I double I'll bother to, so let me know if you
find an error. I also suspect it might even be possible to make an
algorithm which is sub-exponential in the number of digits, but I
haven't look into this much.
At any rate, here's the code which I used to compute all these answers:
-------------------------------------------------------------------------------
class InvertibleList(object):
"""Like a list, but also allows you to efficiently find the index
at which a given element appears. All elements in the list are assumed
to be unique. Python probably has something like this built in, but it
was easy enough to code that I just implemented it myself."""
def __init__(self, items=[]):
self.values = []
self.invValues = {}
self.extend(items)
def __len__(self):
return len(self.values)
def __getitem__(self, key):
return self.values[key]
def indexOf(self, value):
return self.invValues[value]
def append(self, item):
self.values.append(item)
self.invValues[item] = len(self.values)-1
def extend(self, items):
for item in items:
self.append(item)
def __contains__(self, value):
return value in self.invValues
def __eq__(self, other):
if len(self) != len(other): return False
for v1, v2, in zip(self.values, other.values):
if v1 != v2: return False
return True
def __hash__(self):
h = hash(len(self))
for i, v in enumerate(self.values):
h ^= hash(i) + hash(v)
return h
def __str__(self):
return str(self.values)
class Orbit(object):
"""Represents the orbit which a value takes under the composition of a
function in a finite field. For convienence you can give the value and
the function to be composed as parameters to the constructor."""
def __init__(self, n=None, f=None):
self.prefix = InvertibleList()
self.loop = InvertibleList()
if n is not None:
assert f is not None
# generate values until we hit a repeat
o = InvertibleList()
o.append(n)
n = f(n)
while n not in o:
o.append(n)
n = f(n)
# partition o into perfix and loop components
ind = o.indexOf(n)
for i in xrange(ind):
self.prefix.append(o[i])
for i in xrange(ind,len(o)):
self.loop.append(o[i])
def itemFrom(self, n, a):
"""Get the a'th item after the appearance on n in this orbit."""
if n in self.loop:
nInd = self.loop.indexOf(n)
return self.loop[(a+nInd) % len(self.loop)]
else:
assert n in self.prefix
nInd = self.prefix.indexOf(n)
nInd2 = a + nInd
if nInd2 < len(self.prefix):
return self.prefix[nInd2]
else:
return self.loop[(nInd2-len(self.prefix)) % len(self.loop)]
def __str__(self):
return str(self.prefix) + "|" + str(self.loop)
def __len__(self):
return len(self.loop)
def __eq__(self, other):
return (self.prefix == other.prefix) and (self.loop == other.loop)
def __hash__(self):
return hash(self.prefix) ^ hash(self.loop)
def reduceOrbit(n, o1):
"""Given an orbit for f, returns an orbit of n under the function
f^n(n). This assumes n is in the orbit o1, and that the sizes of
these orbits behave nicely."""
o2 = Orbit(n, lambda i: o1.itemFrom(i,i))
assert len(o1.loop) % len(o2.loop) == 0
return o2
def getLastDigits(n, numLevels, numDigits):
mod = 10**numDigits
o = Orbit(2, lambda i: (i+1) % mod)
for i in xrange(1, numLevels):
o = reduceOrbit(n, o)
return o.itemFrom(n, n)
def getLastDigitsOrbit(n, numDigits):
mod = 10**numDigits
metaOrbit = Orbit(
Orbit(2, lambda i: (i+1) % mod),
lambda orb: reduceOrbit(n, orb))
return metaOrbit
#-----------------------------[ main ]----------------------------#
if __name__ == "__main__":
numDigits = 5
print "These are the last five digits for the case with five nested
for-loops:"
print getLastDigits(2, 5, numDigits)
print
print "The last five digits for the case with 10^100 nested for-loops:"
metaOrbit = getLastDigitsOrbit(2, numDigits)
print metaOrbit.itemFrom(metaOrbit.prefix[0], 10**100).itemFrom(2,2)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
