

A350228


Multiplicative Van Eck sequence: for n >= 2, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = (nm)*a(n); otherwise a(n+1) = 1. Start with a(1)=1 and a(2)=0.


8



1, 0, 1, 2, 1, 2, 4, 1, 3, 1, 2, 10, 1, 3, 15, 1, 3, 9, 1, 3, 9, 27, 1, 4, 68, 1, 3, 21, 1, 3, 9, 90, 1, 4, 40, 1, 3, 21, 210, 1, 4, 28, 1, 3, 21, 147, 1, 4, 28, 196, 1, 4, 16, 1, 3, 33, 1, 3, 9, 252, 1, 4, 40, 1120, 1, 4, 16, 224, 1, 4, 16, 64, 1, 4, 16, 64, 256, 1, 5, 1, 2, 140
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Theorem 1: There are infinitely many 1's.
Proof: Suppose not. At each successive term, the sequence either grows or returns a 1. If no 1's occur after a certain term called x, then the sequence is monotonically increasing after x. It can be shown that the series grows at least as fast as the factorial between ones. Then for some sufficiently large n > x, a(n) must be greater than any term to appear in the sequence thus far. And a 1 would be returned as the next term.
Theorem 2: If a(n)=k, and k != 1, then an upper bound for the number of terms from the previous 1 to the nth term is the length of the longest factoring of k such that the mth factor is at least equal to m. Call this f(n). If a(n)=1, then the last 1 is at most f(a(n1))+1 terms away.
Proof: This is because the term a(n) can be represented as x(1)*x(2)*...*x(m), with x(i) being the last time a(nm+i1) was seen in the sequence. Because you must cross at least the last 1 to get to the previous a(n), x(i) >= i. So the longest string of x(i)'s that can exist is one where the ith factor is greater than or equal to i. The factors are not necessarily prime. The "longest factoring" (f(n)) refers to the longest string of numbers (x(1)*x(2)*...*x(m)) that can be multiplied to arrive at n.
Theorem 3: If a(n) is prime then a(n2) is appearing in the sequence for the first time.
Proof: Suppose a(n) is prime. Then a(n1) must be 1 or it must be a nontrivial divisor of a(n), unless a(n) = 1 (or the trivial case that a(n) = 0). There are no nontrivial divisors of prime numbers so a(n1) must equal 1. It follows then that a(n2) is appearing for the first time in the sequence because a(n1) = 1.


LINKS

Michael De Vlieger, Loglog scatterplot of a(n) for n = 1..2^16, labeling and showing records in red, and labeling and showing first instances of differences of positions of 1's in blue.


MATHEMATICA

f[1]=1; f[n_]:=0; f2[n_]:=0; a:=(Block[{q=f2[x]}, If[q!=0, s[#]=(#1q)*(x), s[#]=1]])&; s[1]=1; s[2]=0; x=0; data=Reap[Sow[1]; Sow[0]; Do[Sow[x=a[n]]; f2[x]=f[x]; f[x]=n, {n, 3, 1000000}]][[2, 1]]


PROG

(Python)
from itertools import islice, count
def A350228gen():
yield from (1, 0)
b, bdict = 0, {1:(1, ), 0:(2, )}
for n in count(3):
if len(l := bdict[b]) > 1:
m = (n1l[2])*b
if m in bdict:
bdict[m] = (bdict[m][1], n)
else:
bdict[m] = (n, )
b = m
else:
bdict[1] = (bdict[1][1], n)
b = 1
yield b
(PARI) findm(list, n) = {forstep (m=n1, 1, 1, if (list[m] == list[n], return(m))); return(0); }
lista(nn) = {my(list = List([1, 0])); for (n=3, nn, my(m = findm(list, n1)); if (m, listput(list, (n1m)*list[n1]), listput(list, 1); ); ); Vec(list); } \\ Michel Marcus, Jan 16 2022


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



