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

3, 11, 52, 252, 1253, 6253, 31254, 156254, 781255, 3906255, 19531256, 97656256, 488281257, 2441406257, 12207031258, 61035156258, 305175781259, 1525878906259, 7629394531260, 38146972656260, 190734863281261, 953674316406261, 4768371582031262, 23841857910156262

Offset

1,1

Comments

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

Links

Table of n, a(n) for n=1..24.

Wikipedia, Multiplicative order

Index entries for linear recurrences with constant coefficients, signature (6,-4,-6,5).

Formula

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

Example

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.

Prog

(Python)
def a(n):
    s, x, M = set(), 1, 10**n
    while x not in s: s.add(x); x = (x<<2)%M
    return len(s), x
print([a(n) for n in range(1, 11)]) # Michael S. Branicky, Apr 22 2023
(Python)
def A362468(n): return (n+1>>1)+(5**(n-1)<<1) # Chai Wah Wu, Apr 24 2023
(PARI) a(n)=(n+1)\2*2*5^(n-1) \\ Charles R Greathouse IV, Apr 28 2023

Crossrefs

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

Sequence in context: A244754 A129097 A319155 * A292927 A367046 A179322

Adjacent sequences: A362465 A362466 A362467 * A362469 A362470 A362471

Keyword

nonn,base,easy

Author

Gil Moses, Apr 21 2023

Extensions

a(13) and beyond from Michael S. Branicky, Apr 22 2023

Status

approved