A348040 -id:A348040 - cp's OEIS frontend

A348041 Square array read by antidiagonals. A(n,k) is the nearest common ancestor of n and k in the Doudna tree (A005940).

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 2, 2, 3, 2, 1, 1, 2, 3, 2, 5, 2, 3, 2, 1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 1, 1, 2, 2, 4, 5, 6, 5, 4, 2, 2, 1, 1, 2, 3, 4, 2, 3, 3, 2, 4, 3, 2, 1, 1, 2, 3, 2, 2, 2, 7, 2, 2, 2, 3, 2, 1, 1, 2, 3, 2, 5, 2, 2, 2, 2, 5, 2, 3, 2, 1

Offset: 1

Antti Karttunen and Peter Munn, Sep 27 2021

Array is symmetric and is read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ... .
Also the nearest common ancestor of n and k in the tree depicted in A163511 (the mirror image of the Doudna tree).
The first fork in the Doudna tree separates numbers divisible by the square of their largest prime factor (on one main branch) from other numbers greater than 2 (on the other main branch). If n and m are on different main branches then A(n, m) = 2.
In more general terms A(.,.) can be considered as a binary operation that evaluates certain differences between the prime factors of its operands. To start, compare the largest prime factor of each operand with the 2nd largest prime factor. As described above, 2 is the result if these 2 factors are the same in one operand, but are different in the other operand; otherwise 3 is the result if these 2 factors are consecutive primes in one operand, but are nonconsecutive primes in the other operand. Further cases are covered in the examples, but note it is the difference between the indices of the prime numbers that is significant.

			The top left 17x17 corner of the array:
  n/k |  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17
------+-------------------------------------------------------------
    1 |  1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,
    2 |  1, 2, 2, 2, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,
    3 |  1, 2, 3, 2, 3, 3, 3, 2, 2,  3,  3,  3,  3,  3,  3,  2,  3,
    4 |  1, 2, 2, 4, 2, 2, 2, 4, 4,  2,  2,  2,  2,  2,  2,  4,  2,
    5 |  1, 2, 3, 2, 5, 3, 5, 2, 2,  5,  5,  3,  5,  5,  3,  2,  5,
    6 |  1, 2, 3, 2, 3, 6, 3, 2, 2,  3,  3,  6,  3,  3,  6,  2,  3,
    7 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5,  7,  3,  7,  7,  3,  2,  7,
    8 |  1, 2, 2, 4, 2, 2, 2, 8, 4,  2,  2,  2,  2,  2,  2,  8,  2,
    9 |  1, 2, 2, 4, 2, 2, 2, 4, 9,  2,  2,  2,  2,  2,  2,  4,  2,
   10 |  1, 2, 3, 2, 5, 3, 5, 2, 2, 10,  5,  3,  5,  5,  3,  2,  5,
   11 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5, 11,  3, 11,  7,  3,  2, 11,
   12 |  1, 2, 3, 2, 3, 6, 3, 2, 2,  3,  3, 12,  3,  3,  6,  2,  3,
   13 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5, 11,  3, 13,  7,  3,  2, 13,
   14 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5,  7,  3,  7, 14,  3,  2,  7,
   15 |  1, 2, 3, 2, 3, 6, 3, 2, 2,  3,  3,  6,  3,  3, 15,  2,  3,
   16 |  1, 2, 2, 4, 2, 2, 2, 8, 4,  2,  2,  2,  2,  2,  2, 16,  2,
   17 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5, 11,  3, 13,  7,  3,  2, 17,
.
The nearest common ancestor of 7 and 15 in the Doudna tree (see diagram in the links and A005940) is 3, thus A(7,15) = A(15,7) = 3.
The nearest common ancestor of 12 and 15 in the Doudna tree is 6, thus A(12,15) = A(15,12) = 6.
The nearest common ancestor of 4 and 27 is 4 because 27 is a descendant of 4 in the Doudna tree, thus A(4,27) = A(27,4) = 4.
Example without reference to the Doudna tree: (Start)
The method below works in general for A(.,.) considered as a binary operation, but we use A(20, 42) as our example.
(1) Write each operand as a product of primes in nondecreasing order, convert to a tuple of prime indices, decrement each index, take first differences, then reverse the order:
  20 = 2*2*5 = prime(1) * prime(1) * prime(3) -> (1,1,3) -> (0,0,2) -> (0,0,2) -> (2,0,0);
  42 = 2*3*7 = prime(1) * prime(2) * prime(4) -> (1,2,4) -> (0,1,3) -> (0,1,2) -> (2,1,0).
(2) Truncate each tuple after the first elements that differ between them (or at the length of the shorter tuple):
  (2,0,0) -> (2,0); (2,1,0) -> (2,1).
(3) Choose the lesser tuple: (2,0).
(4) Determine which number would generate this tuple by the process from step (1):
  10 = 2*5 = prime(1) * prime(3) -> (1,3) -> (0,2) -> (0,2) -> (2,0).
This gives A(20, 42) = 10.
(End)

Michael De Vlieger, Doudna Tree diagram showing 8 rows.
Index entries for sequences computed from indices in prime factorization

Cf. A000027 (main diagonal).
Cf. A000040, A005940, A052126, A061395, A064989, A070003, A102750, A156552, A163511, A241917, A347879 [= a(n,sigma(n))], A348040, A348041, A348042, A348043, A348044 [= a(n,n^2)].
Cf. also A341510, A347380, A347381.

up_to = 105;
Abincompreflen(n, m) = { my(x=binary(n),y=binary(m),u=min(#x,#y)); for(i=1,u,if(x[i]!=y[i],return(i-1))); (u);};
Abinprefix(n,k) = { my(digs=binary(n)); fromdigits(vector(k,i,digs[i]),2); };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
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
A348040sq(x,y) = Abincompreflen(A156552(x), A156552(y));
A348041sq(x,y) = A005940(1+Abinprefix(A156552(x),A348040sq(x,y)));
A348041list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A348041sq(col,(a-(col-1))))); (v); };
v348041 = A348041list(up_to);
A348041(n) = v348041[n];

\\ A348041sq can be defined also as:
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));
A348041sq(x,y) = if(1==x||1==y,1, my(lista=List([]), i, k=x, stemvec, h=y); while(k>1, listput(lista,k); k = A252463(k)); stemvec = Vecrev(Vec(lista)); while(1, if((i=vecsearch(stemvec,h))>0, return(stemvec[i])); h = A252463(h)));

A(n, 1) = A(1, n) = 1; otherwise if A241917(n) <> A241917(m) then A(n, m) = A000040(1 + min(A241917(2*n), A241917(2*m))); otherwise A(n, m) = x * A000040(A061395(x)+A241917(n)), where x = A(A052126(n), A052126(m)).
A(i, j) = A(j, i).
A(n, n) = n.
A(2, n) = 2 for all n > 1.
A(p, q) = min(p, q) for any primes p and q.
A(A070003(n), A102750(m)) = 2.
A(u^2, v^2) = A(u, v)^2.
A(4k+2, 6k+3) = A064989(2k+1) for all k >= 1.

A347380 Length of the common prefix in the binary expansions of A156552(n) and A332221(n) = A156552(sigma(n)).

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 1, 1, 1, 1, 2, 2, 4, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 3, 1, 6, 2, 1, 1, 1, 2, 1, 3, 1, 8, 2, 4, 2, 3, 2, 5, 3, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 2, 2, 11, 2, 3, 1, 3, 1, 7, 3, 2, 1, 1, 1, 12, 7, 1, 2, 3, 3, 3, 3, 2, 3, 3, 3, 1, 4, 2, 2, 2, 2, 3, 3, 1, 1, 2, 2, 1, 1, 4, 1, 6, 1, 6, 2, 3

Offset: 1

Antti Karttunen, Aug 30 2021

nonn

Cf. A000203, A156552, A252464, A332221, A347381, A348040.

Abincompreflen(n, m) = { my(x=binary(n),y=binary(m),u=min(#x,#y)); for(i=1,u,if(x[i]!=y[i],return(i-1))); (u);};
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
A347380(n) = Abincompreflen(A156552(n), A156552(sigma(n)));

a(n) = A252464(n) - A347381(n).

a(n) = A348040(n, A000203(n)). - Antti Karttunen, Jan 30 2022

A347879 The nearest common ancestor of n and sigma(n) in the Doudna tree (A005940).

Original entry on oeis.org

1, 2, 2, 2, 3, 6, 2, 2, 2, 2, 3, 3, 7, 3, 6, 2, 2, 2, 5, 10, 2, 2, 3, 6, 2, 5, 2, 28, 3, 2, 2, 2, 3, 2, 6, 2, 19, 3, 7, 3, 5, 3, 11, 5, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 3, 5, 3, 3, 3, 31, 3, 5, 2, 5, 2, 17, 5, 3, 2, 2, 2, 37, 17, 2, 3, 6, 5, 5, 5, 4, 5, 5, 5, 2, 7, 3, 3, 3, 3, 5, 5, 2, 2, 3, 3, 2, 2, 7, 2, 13, 2

Offset: 1

Antti Karttunen, Oct 13 2021

nonn

The fixed points of this sequence is given by the union of {2} and A336702.
The positions x such that a(x) = A252463(x) is given by the union of {1} and A347391.
The positions x such that a(x) = A252463(A252463(x)) is given by the union of {1} and A347392.

Cf. A000203, A005940, A252463, A332221, A336702, A347381, A347391, A347392, A348040, A348041.

A347879(n) = A348041sq(n,sigma(n)); \\ Needs also code from A348041.

a(n) = A348041(n, A000203(n)).

A356156 The nearest common ancestor of n and gcd(n, sigma(n)) in the Doudna tree (A005940).

Original entry on oeis.org

1, 1, 1, 1, 1, 6, 1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 1, 2, 1, 12, 1, 2, 1, 28, 1, 6, 1, 1, 3, 2, 1, 1, 1, 2, 1, 10, 1, 3, 1, 2, 3, 2, 1, 2, 1, 1, 3, 2, 1, 2, 1, 2, 1, 2, 1, 6, 1, 2, 1, 1, 1, 3, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 5, 1, 2, 3, 2, 1, 2, 5, 2, 1, 2, 5, 12, 1, 1, 3, 1, 1, 3, 1, 2, 3

Offset: 1

Antti Karttunen, Jul 30 2022

nonn

Cf. A000203, A007691 (fixed points), A009194, A348040, A348041.

Cf. also A347879, A356157, A356158, A356306.

Abincompreflen(n, m) = { my(x=binary(n),y=binary(m),u=min(#x,#y)); for(i=1,u,if(x[i]!=y[i],return(i-1))); (u);};
Abinprefix(n,k) = { my(digs=binary(n)); fromdigits(vector(k,i,digs[i]),2); };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
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
A348040sq(x,y) = Abincompreflen(A156552(x), A156552(y));
A348041sq(x,y) = A005940(1+Abinprefix(A156552(x),A348040sq(x,y)));
A356156(n) = A348041sq(n,gcd(n, sigma(n)));

a(n) = A348041(n, A009194(n)) = A348041(n, gcd(n, A000203(n))).

A356157 The nearest common ancestor of sigma(n) and gcd(n, sigma(n)) in the Doudna tree (A005940).

Original entry on oeis.org

1, 1, 1, 1, 1, 6, 1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 1, 3, 1, 2, 1, 2, 1, 6, 1, 2, 1, 28, 1, 2, 1, 1, 3, 2, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 3, 2, 1, 2, 1, 1, 2, 2, 1, 6, 1, 2, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 2, 3, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 28, 1, 2, 3, 2, 1, 2, 7, 2, 1, 2, 3, 3, 1, 1, 3, 1, 1, 2, 1, 2, 3

Offset: 1

Antti Karttunen, Jul 30 2022

nonn

Cf. A000203, A009194, A336702 (fixed points), A348040, A348041.

Cf. also A347879, A356156, A356307.

Abincompreflen(n, m) = { my(x=binary(n),y=binary(m),u=min(#x,#y)); for(i=1,u,if(x[i]!=y[i],return(i-1))); (u);};
Abinprefix(n,k) = { my(digs=binary(n)); fromdigits(vector(k,i,digs[i]),2); };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
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
A348040sq(x,y) = Abincompreflen(A156552(x), A156552(y));
A348041sq(x,y) = A005940(1+Abinprefix(A156552(x),A348040sq(x,y)));
A356157(n) = A348041sq(sigma(n),gcd(n, sigma(n)));

A374481 The distance from prime(n) to the nearest common ancestor of prime(n) and 1+prime(n) in the Doudna-tree (A005940).

Original entry on oeis.org

0, 1, 1, 3, 3, 2, 6, 5, 7, 8, 10, 4, 10, 9, 13, 15, 15, 7, 12, 19, 9, 19, 20, 22, 24, 20, 21, 27, 26, 23, 30, 28, 25, 32, 34, 28, 15, 25, 36, 31, 39, 39, 41, 19, 41, 45, 31, 44, 42, 43, 46, 50, 52, 51, 42, 52, 55, 51, 25, 46, 41, 61, 61, 59, 28, 51, 44, 67, 60, 68, 55, 70, 64, 71, 69, 74, 73, 32, 61, 69, 79, 35, 82

Offset: 1

Antti Karttunen, Jul 09 2024

nonn

Question: Is there any reasonable lower bound for this sequence?

Considering k that do not occur as terms of this sequence, see also A374214.

Antti Karttunen, Table of n, a(n) for n = 1..100000
Index entries for sequences related to sigma(n)

Cf. A000040, A000203, A005940, A059305, A241917, A252464, A319988, A348040, A347381.

Cf. also A374214, A374482, A374483.

PARI
```
A374481(n) = A347381(prime(n));
```

A241917(n) = if(isprime(n), primepi(n), if(1>=omega(n), 0, my(f=factor(n)); if(f[#f~,2]>1, 0, primepi(f[#f~,1])-primepi(f[(#f~)-1,1]))));
A374481(n) = if(1==n,0,(-1+n-A241917(1+prime(n))));

a(n) = A347381(A000040(n)) = n - A348040(A000040(n), 1+A000040(n)).
For all n >= 1, a(A059305(n)) = A059305(n)-1.
If A319988(1+A000040(n)) then a(n) = n-1.
For n > 1, a(n) = n - A241917(1+prime(n)) - 1. - Peter Munn and Antti Karttunen, Jul 10 2024

A356158 a(n) = gcd(n, A347879(n)).

Original entry on oeis.org

1, 2, 1, 2, 1, 6, 1, 2, 1, 2, 1, 3, 1, 1, 3, 2, 1, 2, 1, 10, 1, 2, 1, 6, 1, 1, 1, 28, 1, 2, 1, 2, 3, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 5, 2, 1, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 3

Offset: 1

Antti Karttunen, Jul 30 2022

nonn

The fixed points of this sequence is given by the union of {2} and A336702.

Cf. A000203, A336702, A347879, A348040, A348041.

Cf. also A356156, A356157, A356308.

Abincompreflen(n, m) = { my(x=binary(n),y=binary(m),u=min(#x,#y)); for(i=1,u,if(x[i]!=y[i],return(i-1))); (u);};
Abinprefix(n,k) = { my(digs=binary(n)); fromdigits(vector(k,i,digs[i]),2); };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
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
A348040sq(x,y) = Abincompreflen(A156552(x), A156552(y));
A348041sq(x,y) = A005940(1+Abinprefix(A156552(x),A348040sq(x,y)));
A347879(n) = A348041sq(n,sigma(n));
A356158(n) = gcd(n, A347879(n));

a(n) = gcd(n, A347879(n)).

cp's OEIS Frontend

A348041 Square array read by antidiagonals. A(n,k) is the nearest common ancestor of n and k in the Doudna tree (A005940).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A347380 Length of the common prefix in the binary expansions of A156552(n) and A332221(n) = A156552(sigma(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A347879 The nearest common ancestor of n and sigma(n) in the Doudna tree (A005940).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A356156 The nearest common ancestor of n and gcd(n, sigma(n)) in the Doudna tree (A005940).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A356157 The nearest common ancestor of sigma(n) and gcd(n, sigma(n)) in the Doudna tree (A005940).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A374481 The distance from prime(n) to the nearest common ancestor of prime(n) and 1+prime(n) in the Doudna-tree (A005940).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A356158 a(n) = gcd(n, A347879(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula