[seqfan] Re: A000108(n) ≡ 1 (mod 6)

[Antti Karttunen]

On Sun Dec 6 09:33:52 CET 2015, Emmanuel Vantieghem wrote at
http://list.seqfan.eu/pipermail/seqfan/2015-December/015784.html:
>
> Dear Ed,
> The periodicity statement is equivalent with the statement that  2  is a primitive root modulo  3^n  for every  n.
> That seems rather easy to prove.

I see it this way:

Taking powers of 2 as 2^k: 1, 2, 4, 8, 16, each further term 2^(k+1) =
2^k + 2^k.

Since log_3(2) < 1, the base-3 expansion of 2^(k+1) can be at most one
digit longer than base-3 expansion of the preceding term 2^k, which
excludes the possibility of arbitrary long carry-chains from the
right. Thus there are only finite number of digit (including the
carry-digit) combinations when doing sum 2^k + 2^k at each step (from
the least significant end to the most significant end), and especially
when computing its most significant digit.
Because the leftmost column is periodic, this forces also all other
columns to be periodic as well.

> The conjecture about the equidistribution of 0, 1, 2 seems less evident.

I think this should be easily worked out with induction. We are doing
here some modulo 3 arithmetic with the digits, "sideways".

See https://oeis.org/A037096 for the "inverted case" (powers of 3
written in base 2) where in the given C-program I have employed a
similar technique and reasoning:
https://oeis.org/A036284/a036284.c.txt
especially the comments before function vertbinpow3.


> Emmanuel.


Best regards,

Antti