A347381 - OEIS

%I #34 Jul 15 2024 23:30:29

%S 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,

%T 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,

%U 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

%N Distance from n to the nearest common ancestor of n and sigma(n) in the Doudna-tree (A005940).

%C 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.

%H Antti Karttunen, <a href="/A347381/b347381.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A347381/a347381.txt">Data supplement: n, a(n) computed for n = 1..65537</a>

%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>

%H <a href="/index/Si#SIGMAN">Index entries for sequences related to sigma(n)</a>

%F 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)).

%o (PARI)

%o A000523(n) = logint(n,2);

%o 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));

%o 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

%o A061395(n) = if(n>1, primepi(vecmax(factor(n)[, 1])), 0);

%o A252464(n) = if(1==n,0,(bigomega(n) + A061395(n) - 1));

%o A347381(n) = (A252464(n)-Abincompreflen(A156552(n), A156552(sigma(n))));

%o (PARI)

%o 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)};

%o A252463(n) = if(!(n%2),n/2,A064989(n));

%o 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)));

%Y Indices of 0 .. 5 in this sequence are given by {2} U A336702, A347391, A347392, A347393, A347394, A374465.

%Y Cf. A000203, A027687, A156552, A252463, A252464, A332221, A347380, A347383, A347384, A347390, A374481 [a(prime(n))], A374482 (indices of records), A374483 (record values).

%Y Cf. A374200, A374204, A374214, A374218, A374219.

%Y Cf. also A336834.

%K nonn,look

%O 1,7

%A _Antti Karttunen_, Aug 30 2021

%E Name changed, old name is now in formula section. - _Antti Karttunen_, Jul 09 2024