cp's OEIS Frontend

The cells are labeled 0,1,2,3,4,5,6,... and we start at time 0 with cell 0 equal to 1, the rest 0.

At each step, the state of a cell is the mod 2 sum of the states of its left and right neighbors at the previous step (subject to the constraint that we only consider cells with nonnegative labels).

a(n) gives the state of the system, read from right to left, converted from binary to decimal.

This is a one-sided version of A038183.

Least k such that A000005(A000010(k)) = n.

From Jon E. Schoenfield, Nov 13 2016: (Start)

For every n > 0, phi(2^n) = 2^(n-1) has exactly n divisors, so a(n) <= 2^n.

For every prime p, since phi(a(p)) has exactly p divisors, phi(a(p)) must be of the form q^(p-1), where q is a prime number. If q >= 3, we would have phi(a(p)) >= 3^(p-1), and since k > phi(k) for every k > 1, we would have a(p) >= 3^(p-1)+1, which would be contradicted by the upper bound a(p) <= 2^p (see above) unless 3^(p-1)+1 <= 2^p, which is true only for p = 2. Thus, for every prime p > 2, phi(a(p)) = 2^(p-1), so a(p) > 2^(p-1). In summary, we can state that, for every prime p > 2:

(1) a(p) is the least k such that phi(k) = 2^(p-1), and

(2) 2^(p-1) < a(p) <= 2^p.

After a(36)=1333, the next few known terms are a(38)=786433, a(39)=42653, a(40)=1763, and a(42)=2993; as shown above, known bounds on a(37) and a(41) are 2^36 < a(37) <= 2^37 and 2^40 < a(41) <= 2^41.

For prime p < 37, a(p) = A001317(p-1).

Observation: for prime p < 37, a(p) is the product of distinct Fermat primes 2^(2^j)+1 for j=0..4, i.e., 3, 5, 17, 257, and 65537 (see A019434), according to the locations of the 1-bits in p-1:

. p-1 in

p a(p) prime factorization of a(p) binary

== ========== =========================== ======

2 3 = 3 1

3 5 = 5 10

5 17 = 17 100

7 85 = 17 * 5 110

11 1285 = 257 * 5 1010

13 4369 = 257 * 17 1100

17 65537 = 65537 10000

19 327685 = 65537 * 5 10010

23 5570645 = 65537 * 17 * 5 10110

29 286331153 = 65537 * 257 * 17 11100

31 1431655765 = 65537 * 257 * 17 * 5 11110

.

This pattern does not continue to p=37, since 2^(2^5)+1 is not prime. (See also A038183 and the observation there from Arkadiusz Wesolowski.) (End)

As noted, for every prime p, phi(a(p))=2^(p-1), decompose a(p) = p_1^(e_1) *...* p_m^(e_m), then phi(a(p)) = p_1^(e_1-1)*(p_1 - 1) * ... * p_m^(e_m-1)*(p_m - 1). Thus a(p) is of the form 2^e * F_(a_1) *...* F_(a_l), where F_(a_i) = 2^(a_i) + 1 denote distinct Fermat primes. If e = 0, a_1 + ... + a_l = p - 1, while if e > 0, e + a_1 + ... + a_l = p. It can be deduced that a(p) = 2^p unless p-1 can be written as a_1 + ... a_l where 2^(a_i) + 1 are distinct Fermat primes. The only Fermat primes known have a_i in {1,2,4,8,16} and it is known that 2^a + 1 is composite for 16 < a < 2^33 (cf. A019434). It follows from the fact that 1 + 2 + 4 + 8 + 16 = 31 that a(p) = 2^p for primes p with 32 < p <= 2^33. - Pjotr Buys, Sep 18 2019

The successive generations of one-dimensional cellular automata rule (k=1,r=2) 1721342310 (hex 66999966) starting from the seed pattern 1.

A007814(a(n))=n. - Robert Israel, Mar 22 2020