cp's OEIS Frontend

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.

%I A090252 #137 Jun 05 2025 04:23:02
%S A090252 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,
%T A090252 67,71,73,55,79,27,49,83,89,97,101,103,107,109,113,127,131,137,139,
%U A090252 149,151,26,157,163,167,173,179,181,191,193,197,199,211,85,121,223,227,57,229
%N 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.
%C A090252 a(n) is coprime to the next n terms. - _David Wasserman_, Oct 24 2005
%C A090252 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.
%C A090252 It appears that a(n) is even iff n = 3*2^k-1 for some k (A083356). - _N. J. A. Sloane_, Nov 01 2014
%C A090252 The even terms in the present sequence are listed in A354255.
%C A090252 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
%C A090252 Comments from _N. J. A. Sloane_, May 23 2022: (Start)
%C A090252 Conjecture 1. A090252 is a subsequence of A354144 (prime powers and semiprimes).
%C A090252 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, ...
%C A090252 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.
%C A090252 Let S_p = list of indices of terms in A090252 that are divisible by the prime p.
%C A090252 Conjecture 3. For a prime p, there are constants v_1, v_2, ..., v_K and c such that
%C A090252    S_p = { v_1, v_2, ..., v_k, lambda*2^i - 1, i >= c}.
%C A090252 For example, from _Michael S. Branicky_'s 10000-term b-file, it appears that:
%C A090252    S_2 = { 3*2^k-1, k >= 0 }  cf. A083329
%C A090252    S_3 = { 2^k-1, k >= 2 }  cf. A000225
%C A090252    S_5 = { 4 then 15*2^k-1 k >= 0 }  cf. A196305
%C A090252    S_7 = { 6, 15, then 33*2^k-1, k >= 0  }
%C A090252    S_11 = { 8, 29, then 61*2^k-1, k >= 0 }
%C A090252    S_13 = { 9, 47, 97*2^n-1, n >= 0 }
%C A090252    S_17 = { 10, 59, 121*2^n-1, n >= 0 }
%C A090252    S_19 = { 12, 63, 129*2^n-1, n >= 0 }
%C A090252    S_23 = { 13, 65, 133*2^n-1, n >= 0 }
%C A090252    S_29 = { 16, 121, 245*2^n-1, n >= 0 }
%C A090252    S_31 = { 17, 131, 265*2^n-1, n >= 0 }
%C A090252 The initial primes p and the corresponding values of lambda are:
%C A090252     p:   2   3   5   7   11   13   17   19   23   29   31
%C A090252 lambda:..3...1..15..33...61...97..121..129..133..245..265
%C A090252 (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.)
%C A090252 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.
%C A090252 Also 10 does not appear, since S_2 and S_5 are disjoint.
%C A090252 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.
%C A090252 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.
%C A090252 (End)
%C A090252 From _N. J. A. Sloane_, Jun 06 2022 (Start)
%C A090252 Theorem: (a) a(n) <= prime(n-1) for all n >= 2 (cf. A354154).
%C A090252   (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.
%C A090252 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.
%C A090252 For example, a(34886) = 408710 (see the b-file) = prime(34886 - A354166(34886)) = prime(34886 - 374) = prime(34512) = 408710.
%C A090252 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).
%C A090252 (End)
%C A090252 If we consider the May 23 2022 comment, note the conjectured indices show near complete overlap with terms of A081026: 1, 2, 3, 5, 6, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 8191. - _Bill McEachen_, Aug 09 2024
%H A090252 Michael S. Branicky, <a href="/A090252/b090252.txt">Table of n, a(n) for n = 1..34886</a>
%H A090252 Russ Cox, <a href="/A354164/a354164.txt">Table of nonprime entries in A090252: n, A090252(n), # of prime factors, n = 1..3527.</a>
%H A090252 Russ Cox, <a href="/A090252/b090252.txt.gz">Table of n, a(n) for n = 1..5764982</a>, up to the first term that is greater than 10^8 [gzipped file]
%H A090252 Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, <a href="http://arxiv.org/abs/2209.04108">The Binary Two-Up Sequence</a>, arXiv:2209.04108 [math.CO], Sep 11 2022.
%H A090252 N. J. A. Sloane, <a href="https://njas.blog/2022/06/03/the-two-up-sequence-a090252/">Blog post about the Two-Up sequence</a>, June 13 2022.
%H A090252 Hugo van der Sanden, <a href="/A249064/a249064.txt">Perl program</a> to calculate this sequence and A249064 (requires Math::Pari)
%H A090252 Hugo van der Sanden, <a href="https://github.com/hvds/seq/blob/master/A249064/A090252">Faster Perl program</a> on github, used to compute 10^9 terms. [Link changed by _N. J. A. Sloane_, Jun 19 2022]
%H A090252 Hugo van der Sanden, <a href="/A354164/a354164_b.txt">Table of nonprime entries in the first 10^9 terms of A090252</a> [See beginning of the file for description. The blog in the above link has comments from _Hugo van der Sanden_ describing the algorithm used to generate this table.]
%t A090252 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 *)
%o A090252 (Python)
%o A090252 from math import gcd, prod
%o A090252 from itertools import count, islice
%o A090252 def agen(): # generator of terms
%o A090252     alst = [1]; aset = {1}; yield 1
%o A090252     mink = 2
%o A090252     for n in count(2):
%o A090252         k, prodall = mink, prod(alst[n-n//2-1:n-1])
%o A090252         while k in aset or gcd(prodall, k) != 1: k += 1
%o A090252         alst.append(k); aset.add(k); yield k
%o A090252         while mink in aset: mink += 1
%o A090252 print(list(islice(agen(), 64))) # _Michael S. Branicky_, May 21 2022
%o A090252 (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
%Y A090252 Cf. A083329, A084937, A196305, A249064, A354146, A354148-A354151, A354154, A354159-A354167, A354255 (even terms), A355893.
%Y A090252 See also A354169, A354764, A354765, A355057.
%Y A090252 See A247665 for the case when the numbers are required to be at least 2. A353730 is another version.
%Y A090252 For a squarefree analog, see A354790, A354791, A354792.
%K A090252 nonn
%O A090252 1,2
%A A090252 _Amarnath Murthy_, Nov 27 2003
%E A090252 More terms from _David Wasserman_, Oct 24 2005