A322809 -id:A322809 - cp's OEIS frontend

A305801 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = 0 if n is an odd prime, with f(n) = n for all other n.

1, 2, 3, 4, 3, 5, 3, 6, 7, 8, 3, 9, 3, 10, 11, 12, 3, 13, 3, 14, 15, 16, 3, 17, 18, 19, 20, 21, 3, 22, 3, 23, 24, 25, 26, 27, 3, 28, 29, 30, 3, 31, 3, 32, 33, 34, 3, 35, 36, 37, 38, 39, 3, 40, 41, 42, 43, 44, 3, 45, 3, 46, 47, 48, 49, 50, 3, 51, 52, 53, 3, 54, 3, 55, 56, 57, 58, 59, 3, 60, 61, 62, 3, 63, 64, 65, 66, 67, 3, 68, 69, 70, 71, 72, 73, 74, 3, 75, 76, 77, 3, 78, 3, 79, 80

Offset: 1

Antti Karttunen, Jun 14 2018

nonn

The original name was: "Filter sequence for a(odd prime) = constant sequences", which stemmed from the fact that for all i, j, a(i) = a(j) => b(i) = b(j) for any sequence b that obtains a constant value for all odd primes A065091.
For example, we have for all i, j:
  a(i) = a(j) => A305800(i) = A305800(j),
  a(i) = a(j) => A007814(i) = A007814(j),
  a(i) = a(j) => A305891(i) = A305891(j) => A291761(i) = A291761(j).
There are several filter sequences "above" this one (meaning that they have finer equivalence class partitioning), for example, we have, for all i, j:
[where odd primes are further distinguished by]
  A305900(i) = A305900(j) => a(i) = a(j),   [whether p = 3 or > 3]
  A319350(i) = A319350(j) => a(i) = a(j),   [A007733(p)]
  A319704(i) = A319704(j) => a(i) = a(j),   [p mod 4]
  A319705(i) = A319705(j) => a(i) = a(j),   [A286622(p)]
  A331304(i) = A331304(j) => a(i) = a(j),   [parity of A000720(p)]
  A336855(i) = A336855(j) => a(i) = a(j).   [distance to the next larger prime]

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

Cf. A000720, A065091, A305800, A305900.
Cf. A305900, A319350, A319704, A319705, A331304, A336855 (sequences with finer equivalence class partitioning).
Cf. A305800, A305890, A305891, A305896, A318500, A318888, A319346, A319347, A319349, A319701, A322591, A322809, A322810, A323078, A323367, A323082, A323369, A323370, A323371, A323374, A323400, A324401, A326199, A326201, A326203, A326203, A328470, A329608, A331174, A331730, A331301 (sequences with coarser equivalence class partitioning).
Cf. also A003602, A103391, A295300, A305795, A324400, A331300, A336460 (for similar constructions or similarly useful sequences).

Array[If[# <= 2, #, If[PrimeQ[#], 3, 2 + # - PrimePi[#]]] &, 105] (* Michael De Vlieger, Oct 18 2021 *)

A305801(n) = if(n<=2,n,if(isprime(n),3,2+n-primepi(n)));

a(1) = 1, a(2) = 2; for n > 2, a(n) = 3 for odd primes, and a(n) = 2+n-A000720(n) for composite n.

For n > 2, a(n) = 1 + A305800(n).

Name changed and Comment section rewritten by Antti Karttunen, Oct 17 2021

A322805 Lexicographically earliest such sequence a that for all i, j, a(i) = a(j) => f(i) = f(j), where f(1)=0, f(2)=1, f(n)=-1 for odd primes, and f(n) = A252463(n) for any other number.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 26 2018

nonn

For all i, j:
  a(i) = a(j) => A319694(i) = A319694(j),
  a(i) = a(j) => A319699(i) = A319699(j),
  a(i) = a(j) => A319700(i) = A319700(j),
  a(i) = a(j) => A319703(i) = A319703(j),
  a(i) = a(j) => A319989(i) = A319989(j),
  a(i) = a(j) => A320110(i) = A320110(j) => A320111(i) = A320111(j).

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

Cf. A252463.
Cf. A319694, A319699, A319700, A319703, A319989, A320110, A320111.
Cf. also A322807, A322809.

up_to = 65537;
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; };
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));
A322805aux(n) = if(n<=2,n-1,if(isprime(n),-1,A252463(n)));
v322805 = rgs_transform(vector(up_to,n,A322805aux(n)));
A322805(n) = v322805[n];

A322973 Lexicographically earliest such sequence a that a(i) = a(j) => f(i) = f(j) for all i, j, where f(1) = 0, f(n) = -1 if n is an odd prime, and f(n) = A006370(n) for all other numbers.

Original entry on oeis.org

1, 2, 3, 4, 3, 5, 3, 6, 7, 8, 3, 9, 3, 10, 11, 12, 3, 13, 3, 14, 15, 16, 3, 17, 18, 19, 20, 21, 3, 22, 3, 23, 24, 25, 26, 27, 3, 28, 29, 30, 3, 31, 3, 32, 33, 34, 3, 35, 36, 37, 38, 39, 3, 40, 41, 7, 42, 43, 3, 44, 3, 45, 46, 47, 48, 49, 3, 50, 51, 52, 3, 53, 3, 54, 55, 56, 57, 58, 3, 59, 60, 61, 3, 62, 63, 64, 65, 66, 3, 67, 68, 11, 69, 70, 71, 72, 3, 73, 74, 75, 3, 76, 3

Offset: 1

Antti Karttunen, Jan 05 2019

nonn

For all i, j: a(i) = a(j) => A274472(i) = A274472(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A274472, A305801.

See the crossrefs section in A322809 for a list of similarly constructed filter sequences.

up_to = 65537;
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; };
A006370(n) = if(n%2, 3*n+1, n/2);
A322973aux(n) = if(1==n,0,if((n>2)&&isprime(n),-1,A006370(n)));
v322973 = rgs_transform(vector(up_to,n,A322973aux(n)));
A322973(n) = v322973[n];

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.

Original entry on oeis.org

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

A324399 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j >= 1, where f(n) = A000265(n) for all other numbers, except that f(n) = 0 if n is an odd prime, and f(1) = -1 and f(2) = -2.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Mar 01 2019

nonn

For all i, j:

A324401(i) = A324401(j) => a(i) = a(j).

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

Cf. A000040, A000265, A003602, A322809, A324401.

up_to = 65537;
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; };
A000265(n) = (n/2^valuation(n, 2));
Aux324399(n) = if(n<3,-n,if(isprime(n),0,A000265(n)));
v324399 = rgs_transform(vector(up_to, n, Aux324399(n)));
A324399(n) = v324399[n];

cp's OEIS Frontend

A305801 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = 0 if n is an odd prime, with f(n) = n for all other n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A322805 Lexicographically earliest such sequence a that for all i, j, a(i) = a(j) => f(i) = f(j), where f(1)=0, f(2)=1, f(n)=-1 for odd primes, and f(n) = A252463(n) for any other number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A322973 Lexicographically earliest such sequence a that a(i) = a(j) => f(i) = f(j) for all i, j, where f(1) = 0, f(n) = -1 if n is an odd prime, and f(n) = A006370(n) for all other numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

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

A324399 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j >= 1, where f(n) = A000265(n) for all other numbers, except that f(n) = 0 if n is an odd prime, and f(1) = -1 and f(2) = -2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI