login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A347381
Distance from n to the nearest common ancestor of n and sigma(n) in the Doudna-tree (A005940).
28
0, 0, 1, 1, 1, 0, 3, 2, 2, 3, 3, 2, 2, 3, 1, 3, 6, 3, 5, 1, 4, 5, 7, 2, 3, 4, 3, 0, 8, 4, 10, 4, 4, 7, 2, 4, 4, 7, 3, 4, 10, 4, 9, 4, 3, 9, 13, 4, 4, 4, 7, 7, 15, 4, 5, 5, 6, 9, 15, 4, 7, 10, 3, 5, 4, 6, 12, 6, 8, 5, 19, 5, 9, 6, 4, 8, 3, 5, 19, 4, 3, 11, 20, 4, 7, 11, 9, 6, 22, 4, 4, 8, 11, 15, 7, 5, 24, 5, 3, 5, 20
OFFSET
1,7
COMMENTS
a(n) tells about the degree of relatedness between n and sigma(n) in Doudna tree (see the illustration in A005940). It is 0 for those n where sigma(n) is one of the descendants of n, 1 for those n where the nearest common ancestor of n and sigma(n) is the parent of n, 2 for those n where the nearest common ancestor of n and sigma(n) is the grandparent of n, and so on.
FORMULA
a(n) = A252464(n) - A347380(n), where A347380(n) is the length of the common prefix in binary expansions of A156552(n) and A332221(n) = A156552(sigma(n)).
PROG
(PARI)
A000523(n) = logint(n, 2);
Abincompreflen(x, y) = if(!x || !y, 0, my(xl=A000523(x), yl=A000523(y), s=min(xl, yl), k=0); x >>= (xl-s); y >>= (yl-s); while(s>=0 && !bitand(1, bitxor(x>>s, y>>s)), s--; k++); (k));
A156552(n) = {my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ From A156552
A061395(n) = if(n>1, primepi(vecmax(factor(n)[, 1])), 0);
A252464(n) = if(1==n, 0, (bigomega(n) + A061395(n) - 1));
A347381(n) = (A252464(n)-Abincompreflen(A156552(n), A156552(sigma(n))));
(PARI)
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f)};
A252463(n) = if(!(n%2), n/2, A064989(n));
A347381(n) = if(1==n, 0, my(lista=List([]), i, k=n, stemvec, stemlen, sbr=sigma(n)); while(k>1, listput(lista, k); k = A252463(k)); stemvec = Vecrev(Vec(lista)); stemlen = #stemvec; while(1, if((i=vecsearch(stemvec, sbr))>0, return(stemlen-i)); sbr = A252463(sbr)));
CROSSREFS
Indices of 0 .. 5 in this sequence are given by {2} U A336702, A347391, A347392, A347393, A347394, A374465.
Cf. A000203, A027687, A156552, A252463, A252464, A332221, A347380, A347383, A347384, A347390, A374481 [a(prime(n))], A374482 (indices of records), A374483 (record values).
Cf. also A336834.
Sequence in context: A125504 A243929 A350285 * A075392 A069901 A115039
KEYWORD
nonn,look
AUTHOR
Antti Karttunen, Aug 30 2021
EXTENSIONS
Name changed, old name is now in formula section. - Antti Karttunen, Jul 09 2024
STATUS
approved