A036552 -id:A036552 - cp's OEIS frontend

A036554 Numbers whose binary representation ends in an odd number of zeros.

2, 6, 8, 10, 14, 18, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 54, 56, 58, 62, 66, 70, 72, 74, 78, 82, 86, 88, 90, 94, 96, 98, 102, 104, 106, 110, 114, 118, 120, 122, 126, 128, 130, 134, 136, 138, 142, 146, 150, 152, 154, 158, 160, 162, 166, 168, 170, 174

Offset: 1

Tom Verhoeff

Fraenkel (2010) called these the "dopey" numbers.
Also n such that A035263(n)=0 or A050292(n) = A050292(n-1).
Indices of even numbers in A033485. - Philippe Deléham, Mar 16 2004
a(n) is an odious number (see A000069) for n odd; a(n) is an evil number (see A001969) for n even. - Philippe Deléham, Mar 16 2004
Indices of even numbers in A007913, in A001511. - Philippe Deléham, Mar 27 2004
This sequence consists of the increasing values of n such that A097357(n) is even. - Creighton Dement, Aug 14 2004
Numbers with an odd number of 2's in their prime factorization (e.g., 8 = 2*2*2). - Mark Dow, Sep 04 2007
Equals the set of natural numbers not in A003159 or A141290. - Gary W. Adamson, Jun 22 2008
Represents the set of CCW n-th moves in the standard Tower of Hanoi game; and terms in even rows of a [1, 3, 5, 7, 9, ...] * [1, 2, 4, 8, 16, ...] multiplication table. Refer to the example. - Gary W. Adamson, Mar 20 2010
Refer to the comments in A003159 relating to A000041 and A174065. - Gary W. Adamson, Mar 21 2010
If the upper s-Wythoff sequence of s is s, then s=A036554. (See A184117 for the definition of lower and upper s-Wythoff sequences.) Starting with any nondecreasing sequence s of positive integers, A036554 is the limit when the upper s-Wythoff operation is iterated.  For example, starting with s=(1,4,9,16,...) = (n^2), we obtain lower and upper s-Wythoff sequences
  a=(1,3,4,5,6,8,9,10,11,12,14,...) = A184427;
  b=(2,7,12,21,31,44,58,74,...) = A184428.
  Then putting s=a and repeating the operation gives
b'=(2,6,8,10,13,17,20,...), which has the same first four terms as A036554. - Clark Kimberling, Jan 14 2011
Or numbers having infinitary divisor 2, or the same, having factor 2 in Fermi-Dirac representation as a product of distinct terms of A050376. - Vladimir Shevelev, Mar 18 2013
Thus, numbers not in A300841 or in A302792. Equally, sequence 2*A300841(n) sorted into ascending order. - Antti Karttunen, Apr 23 2018

			From _Gary W. Adamson_, Mar 20 2010: (Start)
Equals terms in even numbered rows in the following multiplication table:
(rows are labeled 1,2,3,... as with the Towers of Hanoi disks)
   1,  3,  5,  7,  9, 11, ...
   2,  6, 10, 14, 18, 22, ...
   4, 12, 20, 28, 36, 44, ...
   8, 24, 40, 56, 72, 88, ...
   ...
As shown, 2, 6, 8, 10, 14, ...; are in even numbered rows, given the row with (1, 3, 5, 7, ...) = row 1.
The term "5" is in an odd row, so the 5th Towers of Hanoi move is CW, moving disc #1 (in the first row).
a(3) = 8 in row 4, indicating that the 8th Tower of Hanoi move is CCW, moving disc #4.
A036554 bisects the positive nonzero natural numbers into those in the A036554 set comprising 1/3 of the total numbers, given sufficiently large n.
This corresponds to 1/3 of the TOH moves being CCW and 2/3 CW. Row 1 of the multiplication table = 1/2 of the natural numbers, row 2 = 1/4, row 3 = 1/8 and so on, or 1 = (1/2 + 1/4 + 1/8 + 1/16 + ...). Taking the odd-indexed terms of this series given offset 1, we obtain 2/3 = 1/2 + 1/8 + 1/32 + ..., while sum of the even-indexed terms is 1/3. (End)

T. D. Noe, Table of n, a(n) for n = 1..1000
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550 (see d(n) on page 501).
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
A. S. Fraenkel, Home Page
Aviezri S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Eric Sopena, i-Mark: A new subtraction division game, arXiv:1509.04199 [cs.DM], 2015.
M. Stoll, Chabauty without the Mordell-Weil group, arXiv preprint arXiv:1506.04286 [math.NT], 2015.
Index entries for 2-automatic sequences.

Indices of odd numbers in A007814. Subsequence of A036552. Complement of A003159. Also double of A003159.

Cf. A000041, A003157, A003158, A005408, A052330, A072939, A079523, A096268 (characteristic function, when interpreted with offset 1), A141290, A174065, A300841.

a036554 = (+ 1) . a079523  -- Reinhard Zumkeller, Mar 01 2012

[2*m:m in [1..100] | Valuation(m,2) mod 2 eq 0]; // Marius A. Burtea, Aug 29 2019

Select[Range[200],OddQ[IntegerExponent[#,2]]&] (* Harvey P. Dale, Oct 19 2011 *)

is(n)=valuation(n,2)%2 \\ Charles R Greathouse IV, Nov 20 2012

def ok(n):
  c = 0
  while n%2 == 0: n //= 2; c += 1
  return c%2 == 1
print([m for m in range(1, 175) if ok(m)]) # Michael S. Branicky, Feb 06 2021

from itertools import count, islice
def A036554_gen(startvalue=1): return filter(lambda n:(~n & n-1).bit_length()&1,count(max(startvalue,1))) # generator of terms >= startvalue
A036554_list = list(islice(A036554_gen(),30)) # Chai Wah Wu, Jul 05 2022

is_A036554 = lambda n: A001511(n)&1==0 # M. F. Hasler, Nov 26 2024

def A036554(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = n+x, bin(x)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return bisection(f,n,n) # Chai Wah Wu, Jan 29 2025

a(n) = A079523(n)+1 = A072939(n)-1.
a(n) = A003156(n) + n = A003157(n) - n = A003158(n) - n + 1. - Philippe Deléham, Apr 10 2004
Values of k such that A091297(k) = 2. - Philippe Deléham, Feb 25 2004
a(n) ~ 3n. - Charles R Greathouse IV, Nov 20 2012 [In fact, a(n) = 3n + O(log n). - Charles R Greathouse IV, Nov 27 2024]
a(n) = 2*A003159(n). - Clark Kimberling, Sep 30 2014
{a(n)} = A052330({A005408(n)}), where {a(n)} denotes the set of integers in the sequence. - Peter Munn, Aug 26 2019

Incorrect equation removed from formula by Peter Munn, Dec 04 2020

A281978 Lexicographically earliest sequence of distinct terms such that, for any n>0, a(2n) is divisible by a(2n-1) and by a(2n+1).

Original entry on oeis.org

1, 4, 2, 6, 3, 15, 5, 20, 10, 40, 8, 24, 12, 36, 9, 54, 18, 90, 30, 120, 60, 180, 45, 135, 27, 162, 81, 324, 108, 216, 72, 144, 16, 64, 32, 96, 48, 240, 80, 320, 160, 640, 128, 384, 192, 576, 288, 864, 432, 1296, 648, 1944, 243, 972, 486, 1458, 729, 3645, 405

Offset: 1

Rémy Sigrist, Feb 04 2017

nonn

To compute a(2n) and a(2n+1): we take the least unseen multiple of a(2n-1) with an unseen proper divisor: the multiple gives a(2n) and the least proger divisor gives a(2n+1).
The first multiple of 2 occurs at n=2: a(2)=4, and a(3)=2.
The first multiple of 3 occurs at n=4: a(4)=6, and a(5)=3,
The first multiple of 5 occurs at n=6: a(6)=15, and a(7)=5.
The first multiple of 7 occurs at n=454: a(454)=5511240, and a(455)=7.
The first multiple of 11 occurs at n=889838: a(889838)=627667978163491186346557440000000000000, and a(889839)=11.
For n>1, let b(n)=least k>0 such that a(n+k)<>a(n)*a(k+1); the first records for b are:
n       b(n)     a(n)
------  -------  ----
2             1  2^2
7             3  5
19            4  2*3*5
33           14  2^4
73           27  5^2
455         243  7
1439        248  7^2
3069        275  7^3
10567       276  7^5
41709       768  7^8
85179      1169  7^10
889839  >110162  11
Conjectures:
- All prime numbers appear in this sequence, in increasing order,
- The derived sequence b is unbounded,
- This sequence is a permutation of the natural numbers.

			The first terms, alongside their p-adic valuations with respect to p=2, 3, 5 and 7 (with 0's omitted), are:
n       a(n)  v2  v3  v5  v7
---  -------  --  --  --  --
1          1
2          4   2
3          2   1
4          6   1   1
5          3       1
6         15       1   1
7          5           1
8         20   2       1
9         10   1       1
10        40   3       1
11         8   3
12        24   3   1
13        12   2   1
14        36   2   2
15         9       2
16        54   1   3
17        18   1   2
18        90   1   2   1
19        30   1   1   1
20       120   3   1   1
21        60   2   1   1
22       180   2   2   1
23        45       2   1
24       135       3   1
...
451   524880   4   8   1
452  1574640   4   9   1
453   787320   3   9   1
454  5511240   3   9   1   1
455        7               1
456       28   2           1
457       14   1           1
458       42   1   1       1

Rémy Sigrist, Table of n, a(n) for n = 1..25000
Rémy Sigrist, PARI program for A281978
Rémy Sigrist, Logarithmic scatterplot of the first million terms

Cf. A036552 (a(2n) is divisible by a(2n-1)).

A092401 List of pairs n, 3n, where n is the least unused number so far.

Original entry on oeis.org

1, 3, 2, 6, 4, 12, 5, 15, 7, 21, 8, 24, 9, 27, 10, 30, 11, 33, 13, 39, 14, 42, 16, 48, 17, 51, 18, 54, 19, 57, 20, 60, 22, 66, 23, 69, 25, 75, 26, 78, 28, 84, 29, 87, 31, 93, 32, 96, 34, 102, 35, 105, 36, 108, 37, 111, 38, 114, 40, 120, 41, 123, 43, 129, 44, 132, 45, 135, 46

Offset: 1

Philippe Deléham, Mar 22 2004

A permutation of the natural numbers.

Cf. A036552, A203602 (inverse).

import Data.List (delete)
a092401 n = a092401_list !! (n-1)
a092401_list = f [1..] where
   f (x:xs) = x : x' : f (delete x' xs) where x' = 3*x
-- Reinhard Zumkeller, Jan 03 2012

A007417 = Select[ Range[100], (# // IntegerDigits[#, 3]& // Split // Last // Count[#, 0]& // EvenQ)&]; a[n_] := If[ OddQ[n], A007417[[(n+1)/2]], 3*A007417[[n/2]] ]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 01 2013, from formula *)

from sympy import integer_log
def A092401(n):
    def f(x): return (n+1>>1)+x-sum(((m:=x//9**i)-2)//3+(m-1)//3+2 for i in range(integer_log(x,9)[0]+1))
    m, k = n+1>>1, f(n+1>>1)
    while m != k: m, k = k, f(k)
    return m if n&1 else 3*m # Chai Wah Wu, Feb 16 2025

a(2n-1) = A007417(n), a(2n) = 3*A007417(n).

A382747 Greedy partition of the positive integers into arithmetic progressions of length at most 4.

Original entry on oeis.org

1, 2, 3, 4, 5, 10, 15, 20, 6, 12, 18, 24, 7, 14, 21, 28, 8, 16, 0, 0, 9, 0, 0, 0, 11, 22, 33, 44, 13, 26, 39, 52, 17, 34, 51, 68, 19, 38, 57, 76, 23, 46, 69, 92, 25, 50, 75, 100, 27, 54, 81, 108, 29, 58, 87, 116, 30, 60, 90, 120, 31, 62, 93, 124, 32, 64, 96, 128, 35, 70, 105, 140, 36, 72, 0, 0, 37, 74, 111, 148, 40, 80, 0, 0

Offset: 1

Jan Snellman, Apr 23 2025

Table by rows, rows have length 4.
Elements are a permutation of positive integers, intermixed with zeros.
Expanded description: Partition the positive integers into arithmetic progressions of the form k, 2k, 3k, 4k, putting every positive integer into the first progressions where it fits, allowing shortened progressions (which are padded with zeros):
  k, 0, 0, 0;
  k, 2k, 0, 0;
  k, 2k, 3k, 0.
Construction:
  1. Start by matrix M with rows indexed by positive integers, columns by 1,2,3,4.
  2. M_ij = i*j.
  3. Proceeding row by row, then column by column, if M_ij = M_rk with r < i, set M_is = 0 for i <= s <= 4; if j=0, remove entire row.
  4. Call the resulting matrix A.
So starting with
M = [ 1  2  3  4]
    [ 2  4  6  8]
    [ 3  6  9 12]
    [ 4  8 12 16]
    [ 5 10 15 20]
    [ 6 12 18 24]
    [ 7 14 21 28]
    [ 8 16 24 32]
    [ 9 18 27 36]
    [10 20 30 40]
    [11 22 33 44]
    [12 24 36 48]
    [13 26 39 52]
    [14 28 42 56]
    [15 30 45 60]
    [16 32 48 64]
    [17 34 51 68]
    [18 36 54 72]
    [19 38 57 76]
    [20 40 60 80]
we arrive at
A = [  1   2   3   4]
    [  5  10  15  20]
    [  6  12  18  24]
    [  7  14  21  28]
    [  8  16   0   0]
    [  9   0   0   0]
    [ 11  22  33  44]
    [ 13  26  39  52]
    [ 17  34  51  68]
    [ 19  38  57  76]
Every row in A is an arithmetic progression (even when 0 is adjoined), and every positive integer occurs at precisely one position.
Thus we get a partition of the positive integers into parts which are arithmetic progressions; using this partition for every prime number p yields a regular (in the sense of Narkiewicz) convolution product on the vector space of arithmetic functions.
The first column of A contains those b such that p^b is primitive.
Alternative construction:
Form an infinite rooted tree T on the nonnegative integers in the following way.
  1. 0 is the root.
  2. Form a branch 0 - 1 - 2 -3 - 4.
  3. Proceed inductively. Add n to end of an existing branch as either
    0 - k=n
    0 - k - 2k=n
    0 - k - 2k - 3k=n
    0 - k - 2k - 3k - 4k=n
    with a preference for smaller k.
  4. After infinitely many steps you have constructed T.
  5. Read the positive integers branch by branch.

			Up to n=15 the branches of the aforementioned tree looks like
  0 -  1 -  2 -  3 - 4,
  0 -  5 - 10 - 15,
  0 -  6 - 12,
  0 -  7 - 14,
  0 -  8,
  0 -  9,
  0 - 11,
  0 - 13;
but since 20=5*4 the second branch may not be complete, so at this stage we only know the first row of the matrix A. Adding 16, 17, 18, 19, 20 we get
  0 -  1 -  2 -  3 -  4,
  0 -  5 - 10 - 15 - 20,
  0 -  6 - 12 - 18,
  0 -  7 - 14,
  0 -  8 - 16,
  0 -  9,
  0 - 11,
  0 - 13,
  0 - 17,
  0 - 19;
and now we know the first two rows of A.

Jan Snellman, Table of n, a(n) for n = 1..20788
W. Narkiewicz, On a class of arithmetical convolutions, Colloq. Math. 10, 1963, pp 81-94.
Jan Snellman, Greedy Regular Convolutions, arXiv:2504.02795 [math.NT], 2025.

First column yields A382748.
A382749(n) = column where n occurs in this matrix.
The case length=2 is A036552, when the latter is interpreted as a matrix with two columns.

def A382747_generator(blocklength=4):
    a_set = set()
    a0 = 1
    while 1:
        while a0 in a_set:
            a_set.remove(a0)
            a0 += 1
        for i in range(1,blocklength+1):
            a = i*a0
            if i != 1 and a in a_set:
                for j in range(blocklength-i+1): yield 0
                break
            yield a
            a_set.add(a) # Pontus von Brömssen, Apr 30 2025

def greedy_matrix(blocklength=2,initial_cols=20):
    m, n = blocklength, initial_cols
    A = matrix(ZZ, m,n, lambda i,j: (i+1)*(j+1))
    for c in range(2, n+1):
        for r in range(1, m+1):
            prev = set(flatten([list() for  in A.columns()[:(c-1)]]))
            v = A[r-1, c-1]
            if v in prev:
                for j in range(r, m+1):
                    A[j-1,c-1] = 0
                break
    return A
def pruned_greedy_matrix(blocklength=2, initial_cols=20):
    A = greedy_matrix(blocklength=blocklength, initial_cols=initial_cols)
    return matrix([ for  in A.columns() if add(_) > 0]).transpose()
pruned_greedy_matrix(blocklength=4, initial_cols=20)

A133640 List of pairs n,4n, where n is the least unused number so far.

Original entry on oeis.org

1, 4, 2, 8, 3, 12, 5, 20, 6, 24, 7, 28, 9, 36, 10, 40, 11, 44, 13, 52, 14, 56, 15, 60, 16, 64, 17, 68, 18, 72, 19, 76, 21, 84, 22, 88, 23, 92, 25, 100, 26, 104, 27, 108, 29, 116, 30, 120, 31, 124, 32, 128, 33, 132, 34, 136, 35, 140, 37, 148, 38, 152, 39, 156

Offset: 1

Jonathan Vos Post, Dec 28 2007

A permutation of the natural numbers. This is to 4 as A036552 is to 2 and as A092401.

			Equivalently, this is row 4 of the array A[k,n] = n-th value of the sequence: list of pairs n,k*n, where n is the least unused number so far. That array begins:
===========================================================================
n...|.1..2..3..4..5..6..7..8..9..10..11..12..13..14..15..16..17..18..19..20
===========================================================================
k=2.|.1..2..3..6..4..8..5.10..7..14...9..18..11..22..12..24..13..26..15..30
k=3.|.1..3..2..6..4.12..5.15..7..21...8..24...9..27..10..30..11..33..13..39
k=4.|.1..4..2..8..3.12..5.20..6..24...7..28...9..36..10..40..11..44..13..52
k=5.|.1..5..2.10..3.15..4.20..6..30...7..35...8..40...9..45..11..55..12..60
k=6.|.1..6..2.12..3.18..4.24..5..30...7..42...8..48...9..54..10..60..11..66
k=7.|.1..7..2.14..3.21..4.28..5..35...6..42...8..56...9..63..10..70..11..77
k=8.|.1..8..2.16..3.24..4.32..5..40...6..48...7..56...9..72..10..80..11..88
k=9.|.1..9..2.18..3.27..4.36..5..45...6..54...7..63...8..72..10..90..11..99
k=10|.1.10..2.20..3.30..4.40..5..50...6..60...7..70...8..80...9..90..11.110
===========================================================================

Cf. A036552, A092401.

L = {1, 4}; Do[x=First[Complement[Range[Max[L] + 1], L]]; L = Join[L, {x, 4*x}], {38}]; L (* Giovanni Resta, Jun 19 2016 *)

Data corrected by Giovanni Resta, Jun 19 2016

cp's OEIS Frontend

A065037 Inverse permutation to A036552.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Formula

Extensions

A036554 Numbers whose binary representation ends in an odd number of zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Python

Python

Python

Formula

Extensions

A281978 Lexicographically earliest sequence of distinct terms such that, for any n>0, a(2n) is divisible by a(2n-1) and by a(2n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A092401 List of pairs n, 3n, where n is the least unused number so far.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A382747 Greedy partition of the positive integers into arithmetic progressions of length at most 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

SageMath

A133640 List of pairs n,4n, where n is the least unused number so far.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions