A064891 -id:A064891 - cp's OEIS frontend

A323161 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j, where f(n<=3) = -n, f(n) = 0 if n-1 is an odd prime, and f(n) = floor((n-1)/2) for all other numbers.

1, 2, 3, 4, 5, 4, 6, 4, 7, 7, 8, 4, 9, 4, 10, 10, 11, 4, 12, 4, 13, 13, 14, 4, 15, 15, 16, 16, 17, 4, 18, 4, 19, 19, 20, 20, 21, 4, 22, 22, 23, 4, 24, 4, 25, 25, 26, 4, 27, 27, 28, 28, 29, 4, 30, 30, 31, 31, 32, 4, 33, 4, 34, 34, 35, 35, 36, 4, 37, 37, 38, 4, 39, 4, 40, 40, 41, 41, 42, 4, 43, 43, 44, 4, 45, 45, 46, 46, 47, 4, 48, 48, 49, 49, 50, 50, 51, 4, 52, 52, 53, 4, 54, 4

Offset: 1

Antti Karttunen, Jan 06 2019

nonn

For all i, j: A322809(i) = A322809(j) <=> a(i+1) = a(j+1).
For all i, j: a(i) = a(j) => b(i) = b(j), where b can be, but is not limited to, any of the following sequences: A029834, A049084, A062590, A063377, A064891, A078442 (A049076), A175663, A175682, A269668, A292936, A323162, many of which are related to counting primes in certain kinds of chains or iterations.
Why does this work? Consider the function f given in the definition: based on its properties, we can deduce from the value of f(n) the following information about n:
  (A) If f(n) = -2, then n is 2, the only even prime,
  (B) If f(n) = -3, then n is 3, the first odd prime,
  (C) If f(n) is zero, then n is an even composite preceded by a prime, but we don't know which even composite exactly,
  (D) If f(n) > 0 and f(1+2*f(n)) = f(2+2*f(n)), then n is either (D1) an odd composite number, or (D2) an even composite number preceded by an odd composite number, and the said composite number in both cases is 1 + 2*f(n),
  (E) If f(n) > 0 and f(1+2*f(n)) <> f(2+2*f(n)), then n is an odd prime > 3, specifically, 1 + 2*f(n).
As this sequence is a restricted growth sequence transform of the said function f, we have a(i) = a(j) <=> f(i) = f(j) for all i, j, thus, even without knowing the value of n, but just a(n), we can find the value of f(n) by searching for the minimal k such that a(k) = a(n), then compute f(k) with that k. Furthermore, any function g defined as g(n) = h(f(n)) [where h is any function], clearly satisfies
  a(i) = a(j) => g(i) = g(j), for all i, j. [*]
For instances of such functions g, we can consider many sequences like those sequences b(n) listed above, that have g(n) = 0 for all composite numbers, and g(p) > 0 for all primes p. This is usually the pattern, but there are exceptions, like A323162, which is the characteristic function of A005381, composites n such that n-1 is also composite. These are precisely the numbers that occur twice in this sequence, while all other numbers (including primes), occur just once, that is, reside in their own singular equivalence classes. Thus, it is not guaranteed that all sequences g matching to this sequence (i.e. those satisfying the implication *), even if not false positives in strict sense, would necessarily have some consistent relation to primes, instead, they might contain any random values at the positions given by A093515. However, in the current OEIS, such sequences are exceedingly rare.

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A305801, A305900, A322809.
Cf. A005381 (numbers that occur twice in this sequence), A093515 (numbers > 1 that occur just once).
Cf. A010051, A029834, A049076, A049084, A062590, A063377, A064891, A078442, A175663, A175682, A269668, A292936, A323162 (some of the matched sequences).

up_to = 10000;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A323161aux(n) = if(n<=3,-n,if(isprime(n-1),0,((n-1)>>1))); \\ This implements the function f of the definition.
v323161 = rgs_transform(vector(up_to,n,A323161aux(n)));
A323161(n) = v323161[n];

a(1) = 1; for n > 1, a(n) = 1 + A322809(n-1).

A064892 "Binary potency" of n-th prime p: length of shortest blocks of 0's inserted between the bits of p required to "dilute" it into a nonprime.

Original entry on oeis.org

1, 2, 2, 1, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 4, 2, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 4, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 3, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1

Offset: 1

Marc LeBrun, Oct 10 2001

Note that the +2 dilution of 3 is not the +1 dilution of 5!

			2nd prime = 3 = 11 -> 0101 = 5 -> 001001 = 9, so a(2) = 2; 3rd prime = 5 = 101 -> 010001 = 17 -> 001000001 = 65, so a(3) = 2

A000040, A064891, A064893.

A064893 Smallest number with "binary potency" of n. Blocks of at least n 0's must be inserted between the bits of a(n) to "dilute" it into a nonprime.

Original entry on oeis.org

1, 2, 3, 29, 149, 4079, 4088027, 1887647351, 355898535581

Offset: 0

Marc LeBrun, Oct 10 2001

Are there values for all a(n)? Is the sequence monotonic?

			1 is nonprime (potency 0) so a(0) = 1.
2 = 10 -> 100 = 4, potency 1, so a(1) = 2.
3 = 11 -> 101 = 5 -> 1001 = 9, potency 2 so a(2) = 3.
Potency 3 first appears for 29, so a(3) = 29; etc.
4088027 dilutes into 5858670956869, 10540679875665334793, 20632314388123853242044433, 41873360515671700575496732442657 and 86420918502629375433474712237244678209, all prime. But the next dilution, 179810732934100666625066494484898891551473793, is composite.

Cf. A000040, A064891, A064892.

isok(k, n) = for (i=1, n, my(b=binary(k), list=List()); for (j=1, #b-1, listput(list, b[j]); for (k=1, i, listput(list, 0););); listput(list, b[#b]); my(x=fromdigits(Vec(list), 2), isp=ispseudoprime(x)); if ((iMichel Marcus, Aug 12 2023

a(6) from Don Reble and Fred W. Helenius (fredh(AT)ix.netcom.com), Oct 11 2001
a(7) from Hans Havermann, Oct 13 2001
a(8) from Michael S. Branicky, Jun 30 2023

cp's OEIS Frontend

A323161 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j, where f(n<=3) = -n, f(n) = 0 if n-1 is an odd prime, and f(n) = floor((n-1)/2) for all other numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A064892 "Binary potency" of n-th prime p: length of shortest blocks of 0's inserted between the bits of p required to "dilute" it into a nonprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

A064893 Smallest number with "binary potency" of n. Blocks of at least n 0's must be inserted between the bits of a(n) to "dilute" it into a nonprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions