IMO problem

[retina]

Originally Posted by LaurV

Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer

But the exponent is 4444 not 4443, and knowledge of the exponent allows us to exclude the answer 10. Don't believe me? Then try going through the analysis without using a program.

Your "cheating" by using a program means you came to the wrong conclusion.

[LaurV]

Originally Posted by retina

Your "cheating" by using a program means you came to the wrong conclusion.

Guilty as stated. If you look to my first post in this thread, it is edited. One of the edited things (beside small stuff I "fix" in all my posts), was to add 10 to the list. I couldn't see it by "analysis" either, haha... That's why the rest of the comment where I stressed out that 10 can be in the list. In those 5 minutes I painted the vecsum(digits... line on the screen "to make sure" and I realized I missed the 10.

[R. Gerbicz]

Originally Posted by LaurV

[/CODE]Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer

And how would you answer for that?
Just to see a close example: s(4444^4368)=72010, so it is collapsing too quickly:
s(s(4444^4368))=10 and s(s(s(4444^4368)))=1.

Notice that if we see "average" expected digit sum for the first number, then in your example:
s(4444^4443) ~ log(4444^4443)/log(10)*4.5=72932 and it is just "too" close to exclude 73000 with this heuristic. (there are other candidates with smaller probability)

[LaurV]

Originally Posted by R. Gerbicz

And how would you answer for that?

Probably, wrong (see my prec post)

[retina]

What is the digital sum³ of 999999999^999999999? IOW: SoD(SoD(SoD(999999999^999999999)))

I hope this breaks your cheating computer programs.

[retina]

Originally Posted by retina

What is the digital sum³ of 999999999^999999999? IOW: SoD(SoD(SoD(999999999^999999999)))

I hope this breaks your cheating computer programs.

Someone has shown me the correct answer via PM. Although posting it here would be just fine, with spoiler tags.

[LaurV]

Originally Posted by retina

I hope this breaks your cheating computer programs.

It does not. What you need is just a bit more RAM. This is just a ~8.9999 billion digits number and you need about 5GB RAM to store it in packed decimal, and you need to do about 30 "square and multiply" (2^30>999999999). iow, like 30 LL iterations of a OBD number...

Of course, approaching the problem like that would be totally stupid, but well... hihi

[henryzz]

Sum 1:
999999999 has 9 digits so 999999999^999999999 has at most 9*999999999 digits.
The maximum possible sum of these digits is 9*9*999999999 = 80999999919.

Sum 2:
It is fairly clear that 79999999999 has the largest sum of digits below 80999999919. This sum is 97.

Sum3:
The number with the largest sum of digits below 97 is 89. This sum is 17.

This leaves an upper bound of 17 for SoD(SoD(SoD(999999999^999999999)))
This leaves the possibility 9 as we know that the SoD function preserves divisibility by 9.

[retina]

Yeah. No computer assistance required.

henryzz and the mystery PMer had the same approach.

[Dr Sardonicus]

Originally Posted by LaurV

Anyhow, if you didn't solve it yet, and want to solve it by yourself, then don't scroll down the code section below).

gp > for(i=1,4444,print(i": "vecsum(digits(vecsum(digits(vecsum(digits(4444^i))))))))
1: 7
2: 4
3: 1
<snip>

Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer

OTOH, the basic argument most solvers used was good enough to prove that the answer would be less than 13 for all i up to 4444, so that for i congruent to 1 (mod 3) the answer is 7, and for i congruent to 2 (mod 3) it is 4. Thus, two-thirds of your computation was unnecessary.

For i divisible by 3, both candidates 1 and 10 are less than the bound 13, so the bound is insufficient to determine the answer. I don't see a simple elegant solution in this case.

[Citrix]

Originally Posted by LaurV

Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer

Hint: 99, 101, 999, 1001...