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

[Antti Karttunen]

On Sun, Dec 6, 2015 at 6:01 PM, Antti Karttunen
<antti.karttunen at gmail.com> wrote:
> 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.

Let's rewrite that as:
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 arbitrarily MANY carries coming from the
right. Thus there are only finite number of digit (including the
carry-digit) combinations _to worry about_ 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.

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

Or should I say "modulo 3 boolean logic"...

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