35
$\begingroup$

Is the sum of digits of $3^{1000}$ a multiple of $7$?

The sum of the digits of $3^{1000}$ can be computed using a computer. It is equal to $2142$, so the answer is positive.

Is there a short proof that the sum of the digits of $3^{1000}$ is a multiple of $7$ without using a computer?

Do you have any advice to solve this type of problem (without programming of course!)?

The results below are known:

  • $3^{1000}$ has $478$ digits, and so the sum is at most $4302$ ($9\cdot478$).

  • This sum is a multiple of $9$.

  • The last four digits of $3^{1000}$ are $0001$.


Context: We are a group of 3 French people working on it since 2007. It's a little exercise I found in my high school book (printed in 2007) which is pretty complicated. The one who created this exercise doesn't know the answer.

This question was previously asked on Math.SE (link).

$\endgroup$
  • 27
    $\begingroup$ "We are a group of 3 french people working on it since 2007." OMG! $\endgroup$ – Ben McKay Sep 26 '17 at 12:50
  • 13
    $\begingroup$ Just so it's clear, the puny number discussed is 3^1000 = 1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001, sum of digits is 2142 = 2 ⋅ 3² ⋅ 7 ⋅ 17. It fits in a comment. $\endgroup$ – Andrej Bauer Sep 26 '17 at 17:23
  • 13
    $\begingroup$ @Joël : We could ask, can the question "Digitsum$(3^n) \equiv 0 \pmod 7$?" be answered in time polynomial in $\log n$? $\endgroup$ – Timothy Chow Sep 26 '17 at 20:15
  • 15
    $\begingroup$ The usual approach for mathematicians is to avoid most questions about decimal digits. $\endgroup$ – Douglas Zare Sep 28 '17 at 2:28
  • 10
    $\begingroup$ I haven't down-voted, but the problem I have with the question, besides the trifle that $1000$ should be any $n$, is that I see no hint that it is more natural or accessible (even euristically) than a myriad similar ones (on sums of digits of $e$, $\sqrt{2}$, or of fibonacci numbers, or (mod $7$) behavior of A077468 and so on). I see no mention here of a trick, tool or puzzling anomaly that might have been remotely helpful, even if on closer inspection it wasn't. Is massive up-voting because a first reading of the questions makes one think it's trivial, and then surprise or guilt follow? $\endgroup$ – Yaakov Baruch Sep 28 '17 at 10:01
11
$\begingroup$

Middle digits of the numbers $3^n$ are unpredictable. At least it is too hard for current techniques to say anything about them. It means that the their sum is unpredictable as well. Some good random number generators are based "digital" ideas.

If we take binary digits of $3^n$ then we immediately get generalization of $(3/2)^n$-problem which is out of reach today.

This picture is taken from a New Kind of Science:enter image description here

The pattern is very similar to "rule 30" picture from the same book:enter image description here

It is expected to have very good pseudorandom properties, see discussion at A New Kind of Science: A 15-Year View.

$\endgroup$
  • 2
    $\begingroup$ I feel this should've been a comment. $\endgroup$ – Wojowu Sep 29 '17 at 9:06
  • $\begingroup$ so you think we should close the topic? $\endgroup$ – Lezraf Sep 29 '17 at 10:47
  • 3
    $\begingroup$ @Lezraf I think yes. One can study this problem as a random number generator. $\endgroup$ – Alexey Ustinov Sep 29 '17 at 10:53
  • 3
    $\begingroup$ @AlexeyUstinov Unfortunately I agree with you... $\endgroup$ – Lezraf Sep 29 '17 at 11:09
8
$\begingroup$

Not an answer, but a series of considerations.

One expects not only the digit sum of 3^n to be a multiple of nine (for integral n greater than 1) but also for the string of digits (in the decimal representation of 3^n) to be somewhat normal in distribution, having roughly the same number of occurrences of each decimal digit. For the given example, the actual digit sum is not far from the expected sum of 2151.

I have not observed the growth of the digit sum of powers of 3, but it should grow linearly with n, subject of course to being a multiple of 9 and not deviating far from the expected value. (Using the posted example for interpolation, I expect the rate of growth of digit sum to average about 2.1 for every increment of n, or to increase by 9 about every 4 steps of n.) Because of this, I would expect 1/7th of the exponents n to yield a multiple of 7 for the digit sum of 3^n, and to occur in runs (or near runs) of length about 4. (So the digit sum may be a multiple of 7 for n=998 or n=1002 as well.) Indeed, if it weren't for the variation, I would expect the digit sums to be multiples of 7 near n=1006.

Gerhard "Not Ready For A Summary" Paseman, 2017.09.26.

$\endgroup$
  • $\begingroup$ Quite interesting. Computing $ 4.5(\log_{10}3^{1000}-1) $ I get $ 2142.5456... $ so perhaps rounding the decimal log to the greatest even integer below it would do the job. $\endgroup$ – Sylvain JULIEN Sep 26 '17 at 18:56
  • 5
    $\begingroup$ @SylvainJULIEN: certainly not! A plot of sum_of_digits($3^n$) shows a lot of random jitter of increasing amplitude (but decreasing amplitude if one plots log(sum_of_digits) instead). I think this question is much like asking whether there is a shortcut to check if the sum of the first $n$ digits of, say, $\pi$ is a multiple of $7$ - but with a misleading number theory flavor that makes one think it possible. $\endgroup$ – Yaakov Baruch Sep 26 '17 at 19:12
  • 1
    $\begingroup$ You use gawk -M too? Gerhard "Prototyping Near To My Heart" Paseman, 2017.09.26. $\endgroup$ – Gerhard Paseman Sep 26 '17 at 19:51
  • 1
    $\begingroup$ @WillSawin. Yes, for $n\le 20000$ the observed sdev (off the expected $4.5\log_{10}(3^n)$) is $1.00452$ times the value you gave, and the small local fluctuations within the interval show no trends or other remarkable features. $\endgroup$ – Yaakov Baruch Sep 27 '17 at 7:16
  • 1
    $\begingroup$ @SylvainJULIEN Even if one expects to have normality, note that the sum of $n$ uniformly distributed digits still has SD $\approx\sqrt{n}$, so much too large for approximations of the sort you're suggesting to be consistent to within the subunit ranges needed for it to do any good. $\endgroup$ – Steven Stadnicki Sep 28 '17 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.