A196305 -id:A196305 - 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.

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

Offset: 1

Amarnath Murthy, Nov 27 2003

nonn

a(n) is coprime to the next n terms. - David Wasserman, Oct 24 2005
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.
It appears that a(n) is even iff n = 3*2^k-1 for some k (A083356). - N. J. A. Sloane, Nov 01 2014
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
Comments from N. J. A. Sloane, May 23 2022: (Start)
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}.
For example, from Michael S. Branicky's 10000-term b-file, it appears that:
   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)
From N. J. A. Sloane, Jun 06 2022 (Start)
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)
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

Michael S. Branicky, Table of n, a(n) for n = 1..34886
Russ Cox, Table of nonprime entries in A090252: n, A090252(n), # of prime factors, n = 1..3527.
Russ Cox, Table of n, a(n) for n = 1..5764982, up to the first term that is greater than 10^8 [gzipped file]
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.
N. J. A. Sloane, Blog post about the Two-Up sequence, June 13 2022.
Hugo van der Sanden, Perl program to calculate this sequence and A249064 (requires Math::Pari)
Hugo van der Sanden, Faster Perl program on github, used to compute 10^9 terms. [Link changed by _N. J. A. Sloane_, Jun 19 2022]
Hugo van der Sanden, Table of nonprime entries in the first 10^9 terms of A090252 [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.]

Cf. A083329, A084937, A196305, A249064, A354146, A354148-A354151, A354154, A354159-A354167, A354255 (even terms), A355893.
See also A354169, A354764, A354765, A355057.
See A247665 for the case when the numbers are required to be at least 2. A353730 is another version.
For a squarefree analog, see A354790, A354791, A354792.

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

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

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
print(list(islice(agen(), 64))) # Michael S. Branicky, May 21 2022

More terms from David Wasserman, Oct 24 2005

A036044 BCR(n): write in binary, complement, reverse.

Original entry on oeis.org

1, 0, 2, 0, 6, 2, 4, 0, 14, 6, 10, 2, 12, 4, 8, 0, 30, 14, 22, 6, 26, 10, 18, 2, 28, 12, 20, 4, 24, 8, 16, 0, 62, 30, 46, 14, 54, 22, 38, 6, 58, 26, 42, 10, 50, 18, 34, 2, 60, 28, 44, 12, 52, 20, 36, 4, 56, 24, 40, 8, 48, 16, 32, 0, 126, 62, 94, 30, 110, 46, 78, 14, 118, 54, 86

Offset: 0

N. J. A. Sloane

a(0) could be considered to be 0 if the binary representation of zero were chosen to be the empty string. - Jason Kimberley, Sep 19 2011
From Bernard Schott, Jun 15 2021: (Start)
Except for a(0) = 1, every term is even.
For each q >= 0, there is one and only one odd number h such that a(n) = 2*q iff n = h*2^m-1 for m >= 1 when q = 0, and for m >= 0 when q >= 1 (see A345401 and some examples below).
a(n) =  0 iff n =    2^m-1 for m >= 1 (Mersenne numbers) (A000225).
a(n) =  2 iff n =  3*2^m-1 for m >= 0 (A153893).
a(n) =  4 iff n =  7*2^m-1 for m >= 0 (A086224).
a(n) =  6 iff n =  5*2^m-1 for m >= 0 (A153894).
a(n) =  8 iff n = 15*2^m-1 for m >= 0 (A196305).
a(n) = 10 iff n = 11*2^m-1 for m >= 0 (A086225).
a(n) = 12 iff n = 13*2^m-1 for m >= 0 (A198274).
For k >= 1, a(n) = 2^k iff n = (2^(k+1)-1)*2^m - 1 for m >= 0.
Explanation for a(n) = 2:
   For m >= 0, A153893(m) = 3*2^m-1 -> 1011...11 -> 0100...00 -> 10 -> 2 where 1011...11_2 is 10 followed by m 1's. (End)

			4 -> 100 -> 011 -> 110 -> 6.

Indranil Ghosh, Table of n, a(n) for n = 0..10000 (first 1024 terms from T. D. Noe)

Cf. A030101, A056539, A329369, A345401.
Cf. A035928 (fixed points), A195063, A195064, A195065, A195066.
Indices of terms 0, 2, 4, 6, 8, 10, 12, 14, 18, 22, 26, 30: A000225 \ {0}, A153893, A086224, A153894, A196305, A086225, A198274, A052996\{1,3}, A291557, A198276, A171389, A198275.

import Data.List (unfoldr)
a036044 0 = 1
a036044 n = foldl (\v d -> 2 * v + d) 0 (unfoldr bc n) where
   bc 0 = Nothing
   bc x = Just (1 - m, x') where (x',m) = divMod x 2
-- Reinhard Zumkeller, Sep 16 2011

A036044:=func; // Jason Kimberley, Sep 19 2011

A036044 := proc(n)
    local bcr ;
    if n = 0 then
        return 1;
    end if;
    convert(n,base,2) ;
    bcr := [seq(1-i,i=%)] ;
    add(op(-k,bcr)*2^(k-1),k=1..nops(bcr)) ;
end proc:
seq(A036044(n),n=0..200) ; # R. J. Mathar, Nov 06 2017

dtn[ L_ ] := Fold[ 2#1+#2&, 0, L ]; f[ n_ ] := dtn[ Reverse[ 1-IntegerDigits[ n, 2 ] ] ]; Table[ f[ n ], {n, 0, 100} ]
Table[FromDigits[Reverse[IntegerDigits[n,2]/.{1->0,0->1}],2],{n,0,80}] (* Harvey P. Dale, Mar 08 2015 *)

a(n)=fromdigits(Vecrev(apply(n->1-n,binary(n))),2) \\ Charles R Greathouse IV, Apr 22 2015

def comp(s): z, o = ord('0'), ord('1'); return s.translate({z:o, o:z})
def BCR(n): return int(comp(bin(n)[2:])[::-1], 2)
print([BCR(n) for n in range(75)]) # Michael S. Branicky, Jun 14 2021

def A036044(n): return -int((s:=bin(n)[-1:1:-1]),2)-1+2**len(s) # Chai Wah Wu, Feb 04 2022

a(2n) = 2*A059894(n), a(2n+1) = a(2n) - 2^floor(log_2(n)+1). - Ralf Stephan, Aug 21 2003

Conjecture: a(n) = (-1)^A023416(n)*b(n) for n > 0 with a(0) = 1 where b(2^m) = (-1)^m*(2^(m+1) - 2) for m >= 0, b(2n+1) = b(n) for n > 0, b(2n) = b(n) + b(n - 2^f(n)) + b(2n - 2^f(n)) for n > 0 and where f(n) = A007814(n) (see A329369). - Mikhail Kurkov, Dec 13 2024

A196940 Primes of the form 15*2^k - 1.

Original entry on oeis.org

29, 59, 239, 479, 15359, 245759, 1966079, 32212254719, 32985348833279, 141670994486089356410879, 18133887294219437620592639, 72535549176877750482370559, 1246151246048358630847319119012823039, 638029437976759618993827388934565396479, 669022355955918694246071548179450845179412479

Offset: 1

Brad Clardy, Oct 07 2011

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..28

Primes in A196305.

Cf. A002237 (k such that 15*2^k-1 is prime).

[a: n in [1..130] | IsPrime(a) where a is 15*2^n-1]; // Vincenzo Librandi, Feb 23 2014

Select[Table[15 2^n - 1, {n, 1, 300}], PrimeQ] (* Vincenzo Librandi, Feb 23 2014 *)

for(n=1,1e3,if(ispseudoprime(t=15<Charles R Greathouse IV, Oct 08 2011

a(n) = A196305(A002237(n)). - Elmo R. Oliveira, Feb 23 2025

A345401 a(n) is the unique odd number h such that BCR(h*2^m-1) = 2n (except for BCR(0) = 1) where BCR is bit complement and reverse per A036044.

Original entry on oeis.org

1, 3, 7, 5, 15, 11, 13, 9, 31, 23, 27, 19, 29, 21, 25, 17, 63, 47, 55, 39, 59, 43, 51, 35, 61, 45, 53, 37, 57, 41, 49, 33, 127, 95, 111, 79, 119, 87, 103, 71, 123, 91, 107, 75, 115, 83, 99, 67, 125, 93, 109, 77, 117, 85, 101, 69, 121, 89, 105, 73, 113, 81, 97, 65, 255, 191

Offset: 0

Bernard Schott, Jun 18 2021

This sequence is a permutation of the odd numbers.
We have BCR(a(n)*2^m-1) = 2n when n = 0 for m >= 1, and BCR(a(n)*2^m-1) = 2n when n >= 1 for m >= 0.
Why this exception when n = 0? As a(0) = 1, we have BCR(1*2^m-1) = 2*0 = 0 only for m >= 1, because, for m = 0, we have BCR(1*2^0-1) = BCR(0) = 1 <> 2*0 = 0.

			a(0) = 1 because BCR(1*2^m-1) = 2*0 = 0 for m >= 1 (A000225).
a(1) = 3 because BCR(3*2^m-1) = 2*1 = 2 for m >= 0 (A153893).
a(2) = 7 because BCR(7*2^m-1) = 2*2 = 4 for m >= 0 (A086224).
Indeed, a(1) = 3 because 3*2^m-1 = 1011..11_2 (i.e., 10 followed by m 1's), whose bit complement is 0100..00, which reverses to 10_2 = 2 = 2*1.
Also, a(43) = 75 because 75*2^m-1 = 100101011..11_2 (i.e., 1001010 followed by m 1's), whose bit complement is 011010100..00, which reverses to 1010110_2 = 86 = 2*43.

Cf. A036044 (BCR), A059894.

When BCR(n) = 0, 2, 4, 6, 8, 10, 12, then corresponding a(n) = h = 1, 3, 7, 5, 15, 11, 13 and numbers h*2^m-1 are respectively in A000225, A153893, A086224, A153894, A196305, A086225, A198274.

a(n) = BCR(2*n) + 1 for n >= 1.

a(n) = 2*A059894(n) + 1 for n >= 1. - Hugo Pfoertner, Jun 18 2021

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A036044 BCR(n): write in binary, complement, reverse.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

Formula

A196940 Primes of the form 15*2^k - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A345401 a(n) is the unique odd number h such that BCR(h*2^m-1) = 2n (except for BCR(0) = 1) where BCR is bit complement and reverse per A036044.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula