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

Improve this question
$\endgroup$
30
  • 29
    $\begingroup$ "We are a group of 3 french people working on it since 2007." OMG! $\endgroup$
    – Ben McKay
    Commented Sep 26, 2017 at 12:50
  • 14
    $\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
    Commented Sep 26, 2017 at 17:23
  • 14
    $\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
    Commented Sep 26, 2017 at 20:15
  • 15
    $\begingroup$ The usual approach for mathematicians is to avoid most questions about decimal digits. $\endgroup$
    – Douglas Zare
    Commented Sep 28, 2017 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
    Commented Sep 28, 2017 at 10:01

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I feel this should've been a comment. $\endgroup$
    – Wojowu
    Commented Sep 29, 2017 at 9:06
  • $\begingroup$ so you think we should close the topic? $\endgroup$
    – Lezraf
    Commented Sep 29, 2017 at 10:47
  • 3
    $\begingroup$ @Lezraf I think yes. One can study this problem as a random number generator. $\endgroup$
    – Alexey Ustinov
    Commented Sep 29, 2017 at 10:53
  • 3
    $\begingroup$ @AlexeyUstinov Unfortunately I agree with you... $\endgroup$
    – Lezraf
    Commented Sep 29, 2017 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.

Improve this answer
$\endgroup$
10
  • $\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
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 at 19:12
  • 1
    $\begingroup$ You use gawk -M too? Gerhard "Prototyping Near To My Heart" Paseman, 2017.09.26. $\endgroup$
    – Gerhard Paseman
    Commented Sep 26, 2017 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
    Commented Sep 27, 2017 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
    Commented Sep 28, 2017 at 0:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .