|
| |
|
|
A090252
|
|
The Two-Up sequence: a(n) is the least positive number not already used that is coprime to the previous floor(n/2) terms.
|
|
39
|
|
|
|
1, 2, 3, 5, 4, 7, 9, 11, 13, 17, 8, 19, 23, 25, 21, 29, 31, 37, 41, 43, 47, 53, 16, 59, 61, 67, 71, 73, 55, 79, 27, 49, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 26, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 85, 121, 223, 227, 57, 229
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
All values up to a(1000000) are either prime powers or semiprimes; this suggests the sequence is unlikely to be a permutation of the integers.
The even terms in the present sequence are listed in A354255.
We have a(1) = 1 and a(2) = 2. At step k >= 2, the sequence is extended by adding two terms: a(2*k-1) = smallest unused number which is relatively prime to a(k), a(k+1), ..., a(2*k-2), and a(2*k) = smallest unused number which is relatively prime to a(k), a(k+1), ..., a(2*k-1). So at step k=2 we add a(3)=3, a(4)=5; at step k=3 we add a(5)=4, a(6)=7; and so on. - N. J. A. Sloane, May 21 2022
Conjecture 1. A090252 is a subsequence of A354144 (prime powers and semiprimes).
Conjecture 2. The terms of A354144 that are missing from A090252 are 6, 10, 14, 15, 22, 33, 34, 35, 38, 39, 46, 51, 58, 62, 65, 69, 74, 77, 82, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 166, 177, 178, 183, 185, 187, 194, 201, 202, 203, 209, 213, 214, 215, 218, 219, 221, ...
But since there is no proof that any one of these numbers is really missing, this list cannot yet have an entry in the OEIS.
Let S_p = list of indices of terms in A090252 that are divisible by the prime p.
Conjecture 3. For a prime p, there are constants v_1, v_2, ..., v_K and c such that
S_p = { v_1, v_2, ..., v_k, lambda*2^i - 1, i >= c}.
S_2 = { 3*2^k-1, k >= 0 } cf. A083329
S_3 = { 2^k-1, k >= 2 } cf. A000225
S_5 = { 4 then 15*2^k-1 k >= 0 } cf. A196305
S_7 = { 6, 15, then 33*2^k-1, k >= 0 }
S_11 = { 8, 29, then 61*2^k-1, k >= 0 }
S_13 = { 9, 47, 97*2^n-1, n >= 0 }
S_17 = { 10, 59, 121*2^n-1, n >= 0 }
S_19 = { 12, 63, 129*2^n-1, n >= 0 }
S_23 = { 13, 65, 133*2^n-1, n >= 0 }
S_29 = { 16, 121, 245*2^n-1, n >= 0 }
S_31 = { 17, 131, 265*2^n-1, n >= 0 }
The initial primes p and the corresponding values of lambda are:
p: 2 3 5 7 11 13 17 19 23 29 31
lambda:..3...1..15..33...61...97..121..129..133..245..265
(This sequence of lambdas does not seem to have any simpler explanation, is not in the OEIS, and cannot be since the terms shown are all conjectural.)
Conjecture 2 is a consequence of Conjecture 3. For example, 6 does not appear in A090252, since the sets S_2 and S_3 are disjoint.
Also 10 does not appear, since S_2 and S_5 are disjoint.
In fact 2*p for 3 <= p <= 11 does not appear, but 26 = 2*13 does appear since S_2 and S_13 have 47 in common.
Assuming the numbers that appear to be missing (see Conjecture 2) really are missing, the numbers that take a record number of steps to appear are 1, 2, 3, 4, 7, 8, 16, 26, 32, 64, 128, 206, 256, 478, 512, 933, ..., and the indices where they appear are 1, 2, 3, 5, 6, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 8191, .... These two sequences are not yet in the OEIS, and cannot be added since the terms are all conjectural.
(End)
Theorem: (a) a(n) <= prime(n-1) for all n >= 2 (cf. A354154).
(b) A stronger upper bound is the following. Let c(n) = A354166(n) denote the number of nonprime terms among a(1) .. a(n). Note c(1)=1. Then a(n) <= prime(n-c(n)) for n <> 7 and 14.
It appears that a(n) = prime(n-c(n)) for almost all n. That is, this is the equation to the line in the graph that contains most of the terms.
For example, a(34886) = 408710 (see the b-file) = prime(34886 - A354166(34886)) = prime(34886 - 374) = prime(34512) = 408710.
Another example: Consider Russ Cox's table of the first N = 5764982 terms. We see that a(5764982) = 99999989 = prime(5761455) = prime(N - 3527) which agrees with c(N) = 3527 (from the first Russ Cox link).
(End)
|
|
|
LINKS
|
Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
|
|
|
MATHEMATICA
|
nn = 120; c[_] = 0; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == 0, AllTrue[Array[a[i - #] &, Floor[i/2]], CoprimeQ[#, k] &]], k++]; Set[{a[i], c[k]}, {k, i}]; If[k == u, While[c[u] > 0, u++]], {i, 2, nn}]; Array[a, nn]] (* Michael De Vlieger, May 21 2022 *)
|
|
|
PROG
|
(Python)
from math import gcd, prod
from itertools import count, islice
def agen(): # generator of terms
alst = [1]; aset = {1}; yield 1
mink = 2
for n in count(2):
k, prodall = mink, prod(alst[n-n//2-1:n-1])
while k in aset or gcd(prodall, k) != 1: k += 1
alst.append(k); aset.add(k); yield k
while mink in aset: mink += 1
(PARI) A090252_first(N, U=[0], L=List())=vector(N, i, for(k=U[1]+1, oo, setsearch(U, k) && next; foreach(L, m, gcd(k, m)>1 && next(2)); bitand(i, 1) || listpop(L, 1); listput(L, k); if( k>U[1]+1, U=setunion(U, [k]), U[1]++; while(#U>1 && U[2]==U[1]+1, U=U[^1])); break); L[#L]) \\ M. F. Hasler, Jun 14 2022
|
|
|
CROSSREFS
|
See A247665 for the case when the numbers are required to be at least 2. A353730 is another version.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
