login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of distinct n-digit suffixes generated by iteratively multiplying an integer by 4, where the initial integer is 1.
3

%I #26 Apr 28 2023 09:52:23

%S 3,11,52,252,1253,6253,31254,156254,781255,3906255,19531256,97656256,

%T 488281257,2441406257,12207031258,61035156258,305175781259,

%U 1525878906259,7629394531260,38146972656260,190734863281261,953674316406261,4768371582031262,23841857910156262

%N Number of distinct n-digit suffixes generated by iteratively multiplying an integer by 4, where the initial integer is 1.

%C This process produces a family of similar sequences when using different constant multipliers. See crossrefs below.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_order">Multiplicative order</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-4,-6,5).

%F a(n) = t + k, where t = A004526(n+1) and k = A020699(n), since 4^t == 4^(t+k) (mod 10^n). Here, t is the "transient" portion and k = ord_5^n(4), the multiplicative order of 4 modulo 5^n, is the period of the orbit. - _Michael S. Branicky_, Apr 22 2023

%e For n = 2, we begin with 1, iteratively multiply by 4 and count the number of terms before the last 2 digits begin to repeat. We obtain 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, ... . The next term is 4194304, which repeats the last 2 digits 04. Thus, the number of distinct terms is a(2) = 11.

%o (Python)

%o def a(n):

%o s, x, M = set(), 1, 10**n

%o while x not in s: s.add(x); x = (x<<2)%M

%o return len(s), x

%o print([a(n) for n in range(1, 11)]) # _Michael S. Branicky_, Apr 22 2023

%o (Python)

%o def A362468(n): return (n+1>>1)+(5**(n-1)<<1) # _Chai Wah Wu_, Apr 24 2023

%o (PARI) a(n)=(n+1)\2*2*5^(n-1) \\ _Charles R Greathouse IV_, Apr 28 2023

%Y Period of powers mod 10^n: A020699 (4), A216099 (3), A216164 (7), A216156 (11).

%K nonn,base,easy

%O 1,1

%A _Gil Moses_, Apr 21 2023

%E a(13) and beyond from _Michael S. Branicky_, Apr 22 2023