A057168 -id:A057168 - cp's OEIS frontend

A263017 n is the a(n)-th positive integer having its binary weight.

1, 2, 1, 3, 2, 3, 1, 4, 4, 5, 2, 6, 3, 4, 1, 5, 7, 8, 5, 9, 6, 7, 2, 10, 8, 9, 3, 10, 4, 5, 1, 6, 11, 12, 11, 13, 12, 13, 6, 14, 14, 15, 7, 16, 8, 9, 2, 15, 17, 18, 10, 19, 11, 12, 3, 20, 13, 14, 4, 15, 5, 6, 1, 7, 16, 17, 21, 18, 22, 23, 16, 19, 24, 25, 17

Offset: 1

Paul Tek, Oct 07 2015

Binary weight is given by A000120.
a(2^k) = k+1 for any k>=0.
a(2^k-1) = 1 for any k>0.
a(A057168(k)) = a(k)+1 for any k>0.
a(A036563(k+1)) = k for any k>0.
Ordinal transform of A000120. - Alois P. Heinz, Dec 23 2018

			The numbers with binary weight 3 are: 7, 11, 13, 14, 19, ...
Hence: a(7)=1, a(11)=2, a(13)=3, a(14)=4, a(19)=5, ...
And more generally: a(A014311(k))=k for any k>0.

Paul Tek, Table of n, a(n) for n = 1..10000
Paul Tek, PERL program for this sequence

One more than A068076.
Cf. A000120, A036563, A057168, A254524, A286478, A286552, A286554, A286558.
Cf. A263109, A263110.

import Data.IntMap (empty, findWithDefault, insert)
a263017 n = a263017_list !! (n-1)
a263017_list = f 1 empty where
   f x m = y : f (x + 1) (insert h (y + 1) m) where
           y = findWithDefault 1 h m
           h = a000120 x
-- Reinhard Zumkeller, Oct 09 2015

a:= proc() option remember; local a, b, t; b, a:=
      proc() 0 end, proc(n) option remember; a(n-1);
        t:= add(i, i=convert(n, base, 2)); b(t):= b(t)+1
      end; a(0):=0; a
    end():
seq(a(n), n=1..120);  # Alois P. Heinz, Dec 23 2018

Perl
```
# See Links section.
```

from math import comb
def A263017(n):
    c, k = 1, 0
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            k += 1
            c += comb(i,k)
    return c # Chai Wah Wu, Mar 01 2023

a(n) = 1 + A068076(n). - Antti Karttunen, May 22 2017

A140977 a(n) is the smallest integer > n that has the same number of (nonleading) zeros in its binary representation as n has.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Aug 17 2008

Permutation of the non-binary powers, cf. A057716. - Reinhard Zumkeller, Aug 15 2010

			4 in binary is 100, which has 2 zeros. Checking the binary representations of the integers > 4: 5 = 101 in binary, which has one 0. 6 = 110 in binary, which has one 0. 7 = 111 in binary, which has zero 0's. 8 = 1000 in binary, which has three 0's. But 9 = 1001 in binary, which has two 0's, the same number of zeros that 4 (= 100 in binary) has. So a(4) = 9.

R. Zumkeller, Table of n, a(n) for n = 1..1000
Rémy Sigrist, PARI program for A140977

Cf. A057168, A023416.

a = {}; For[n = 1, n < 100, n++, i = n + 1; While[ ! DigitCount[i, 2, 0] == DigitCount[n, 2, 0], i++ ]; AppendTo[a, i]]; a (* Stefan Steinerberger, Aug 25 2008 *)
snz[n_]:=Module[{dn=DigitCount[n,2,0],k=n+1},While[DigitCount[k,2,0] != dn, k++]; k]; Array[snz, 100] (* Harvey P. Dale, May 15 2015 *)

PARI
```
See Links section.
```

More terms from Stefan Steinerberger, Aug 25 2008

A171942 Forward van Eck transform of A000120.

Original entry on oeis.org

0, 1, 2, 2, 4, 1, 3, 4, 8, 1, 2, 2, 5, 1, 5, 8, 16, 1, 2, 2, 4, 1, 3, 4, 9, 1, 2, 2, 7, 1, 9, 16, 32, 1, 2, 2, 4, 1, 3, 4, 8, 1, 2, 2, 5, 1, 5, 8, 17, 1, 2, 2, 4, 1, 3, 4, 11, 1, 2, 2, 11, 1, 17, 32, 64, 1, 2, 2, 4, 1, 3, 4, 8, 1, 2, 2, 5, 1, 5, 8, 16, 1, 2, 2, 4, 1, 3, 4, 9, 1, 2, 2, 7, 1, 9, 16, 33, 1, 2, 2

Offset: 1

N. J. A. Sloane, Oct 25 2010

nonn

Assumes that the offset of A000120 has been changed to 1.

Comment from Marc LeBrun, Jan 01 2014: A057168(n) - n (the difference between n and the next number with the same binary weight) matches A171942, "Forward van Eck transform of A000120" (the weight of n). Response from M. F. Hasler, Jan 01 2014: The "forward van Eck transform" is the sequence of gaps to the next term with equal value: FVE(a) = n -> min { m>0 | a(n+m)=a(n) } with the (exceptional) convention that : min {} = 0. (See A171898.) So your observation is exactly the definition.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Transforms

Cf. A000120, A057168, A171898.

a171942 1 = 0
a171942 n = head [m | m <- [1..], a000120 (m + n - 1) == a000120 (n - 1)]
-- Reinhard Zumkeller, Jan 01 2014

def A171942(n): return (((n-1&~(b:=n-1+(a:=n-1&-n+1)))>>a.bit_length())^b)-n+1 # Chai Wah Wu, Mar 06 2025

A243109 a(n) is the largest number smaller than n and having the same Hamming weight as n, or n if no such number exist.

Original entry on oeis.org

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

Offset: 0

Philippe Beaudoin, Aug 20 2014

To calculate a(n), some bits of n are rearranged. The lowest 1-bit which can move down is the 1 of the lowest 10 bit pair in n. This pair becomes 01 in a(n) and any 1's below there move up to immediately below so the decrease is as small as possible. If n has no 10 bit pair (n = 2^k-1) then nothing smaller is possible and a(n) = n. - Kevin Ryde, Mar 01 2021

			From _Kevin Ryde_, Mar 01 2021: (Start)
                           v    vv
     n = 1475 = binary 10111000011    lowest 10 of n
  a(n) = 1464 = binary 10110111000    becomes 01 and
                            ^^^       other 1's below
(End)

Philippe Beaudoin, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 1.24.1 Co-lexicographic (colex) order, function prev_colex_comb(), and second implementation in FXT library bitcombcolex.h (both 0 when no previous rather than a(n) = n).

Cf. A057168 (next of same weight), A066884 (array by weight), A241816 (lowest 10->01).

A243109[n_] := If[# == 0, n, # - 2^(IntegerExponent[#, 2] - IntegerExponent[n+1, 2] - 1)] & [BitAnd[n, n+1]];
Array[A243109, 100, 0] (* Paolo Xausa, Mar 07 2025 *)

a(n) = {my(hn = hammingweight(n)); forstep(k=n-1, 1, -1, if (hammingweight(k) == hn, return (k)); ); return (n); } \\ Michel Marcus, Aug 20 2014

a(n) = my(s=n+1,t=bitand(n,s)); if(t==0,n, t - 1<<(valuation(t,2)-valuation(s,2)-1)); \\ Kevin Ryde, Mar 01 2021

def A243109(n): return c if (c:=((~n&(b:=n-(a:=~n&n+1)))>>a.bit_length())^b) else n # Chai Wah Wu, Mar 06 2025

a(n) = t - 2^(A007814(t) - A007814(n+1) - 1) if t!=0, or a(n) = n if t=0, where t = A129760(n+1) is n with any trailing 1's cleared to 0's and A007814 is the 2-adic valuation. - Kevin Ryde, Mar 01 2021
For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3). - Chai Wah Wu, Mar 07 2025
If n is even, then a(n) = XOR(n,OR(a,a/2)) where a = AND(-n,n+1). - Chai Wah Wu, Mar 08 2025

A295827 a(n) = least odd k > 1 such that n and n*k have the same Hamming weight, or -1 if no such k exists.

Original entry on oeis.org

-1, -1, 3, -1, 13, 3, 3, -1, 57, 13, 35, 3, 21, 3, 3, -1, 241, 57, 7, 13, 13, 35, 39, 3, 169, 21, 5, 3, 21, 3, 3, -1, 993, 241, 11, 57, 7, 7, 5, 13, 3197, 13, 9, 35, 3, 39, 13, 3, 21, 169, 3, 21, 39, 5, 47, 3, 27, 21, 5, 3, 13, 3, 3, -1, 4033, 993, 491, 241

Offset: 1

Rémy Sigrist, Nov 28 2017

The Hamming weight of a number n is given by A000120(n).
Apparently, a(n) = -1 iff n = 2^k for some k >= 0.
Apparently, a(2^n + 1) = A020515(n) for any n > 1.
a(2^n - 1) = 3 for any n > 1.
a(n) = 3 iff n = A077459(k) for some k > 1.
This sequence has similarities with A292849: here we want A000120(n*a(n)) = A000120(n), there we want A000120(n*a(n)) = A000120(a(n)).
For any n > 0, if a(n) > 0 then A292849(a(n)) <= n.

			The first terms, alongside the binary representations of n and of n*a(n), are:
  n     a(n)     bin(n)         bin(n*a(n))
  --    ----     ------         -----------
   1      -1          1                  -1
   2      -1         10                 -10
   3       3         11                1001
   4      -1        100                -100
   5      13        101             1000001
   6       3        110               10010
   7       3        111               10101
   8      -1       1000               -1000
   9      57       1001          1000000001
  10      13       1010            10000010
  11      35       1011           110000001
  12       3       1100              100100
  13      21       1101           100010001
  14       3       1110              101010
  15       3       1111              101101
  16      -1      10000              -10000
  17     241      10001       1000000000001
  18      57      10010         10000000010
  19       7      10011            10000101
  20      13      10100           100000100

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, Logarithmic scatterplot of the sequence for n=1..2^17 and a(n) < 10^18

Cf. A000120, A020515, A057168, A077459, A292849.

f:= proc(n) local k,w;
  if n = 2^padic:-ordp(n,2) then return -1 fi;
  w:= convert(convert(n,base,2),`+`);
  for k from 3 by 2 do
    if convert(convert(n*k,base,2),`+`)=w then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Nov 28 2017

Table[SelectFirst[Range[3, 10^4 + 1, 2], SameQ @@ Map[DigitCount[#, 2, 1] &, {n, n #}] &] /. m_ /; MissingQ@ m -> -1, {n, 68}] (* Michael De Vlieger, Nov 28 2017 *)

A057168(n)=n+bitxor(n, n+n=bitand(n, -n))\n\4+n \\ after M. F. Hasler at A057168
a(n) = n\=2^valuation(n,2); if (n==1, -1, my(w=(n-1)/2); while(1, w=A057168(w); if((2*w+1)%n==0, return((2*w+1)/n))))

def A295827(n):
    if not(n&-n)^n: return -1
    m = n
    while True:
        m = m^((a:=-m&m+1)|(a>>1)) if m&1 else ((m&~(b:=m+(a:=m&-m)))>>a.bit_length())^b
        a, b = divmod(m,n)
        if not b and a&1: return a # Chai Wah Wu, Mar 11 2025

a(2*n) = a(n) for any n > 0.

A319021 Next larger integer with same sum of digits in base 3 as n.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Sep 08 2018

This sequence is the base-3 variant of A057168 (base-2) and of A228915 (base-10).

All integers except those in A062318 appear in this sequence.

			The first terms, alongside the ternary representations of n and of a(n), are:
  n   a(n)  ter(n)  ter(a(n))
  --  ----  ------  ---------
   1     3      1     10
   2     4      2     11
   3     9     10    100
   4     6     11     20
   5     7     12     21
   6    10     20    101
   7    11     21    102
   8    14     22    112
   9    27    100   1000
  10    12    101    110
  11    13    102    111
  12    18    110    200
  13    15    111    120
  14    16    112    121
  15    19    120    201

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Cf. A053735, A057168, A062318, A228915.

nli3[n_]:=Module[{nd3=Total[IntegerDigits[n,3]],k=n+1},While[Total[IntegerDigits[k,3]]!=nd3,k++];k]; Array[nli3,70] (* Harvey P. Dale, Jun 27 2023 *)

a(n, base=3) = my (c=0); for (w=0, oo, my (d=n % base); if (d+1 < base && c, return ((n+1)*base^w + ((c-1)%(base-1) + 1)*base^((c-1)\(base-1))-1), c += d; n \= base))

def a(n, base=3):
    c, b, w = 0, base, 0
    while True:
        d = n%b
        if d+1 < b and c:
            return (n+1)*b**w + ((c-1)%(b-1)+1)*b**((c-1)//(b-1))-1
        c += d; n //= b; w += 1
print([a(n) for n in range(1, 67)]) # Michael S. Branicky, Jul 10 2022 after Rémy Sigrist

a(3^k) = 3^(k+1) for any k >= 0.

A053735(a(n)) = A053735(n).

A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 17, 18, 18, 18, 18, 19

Offset: 1

Bernard Schott, Dec 28 2020

This sequence is inspired by the 3rd problem, proposed by Romania, during the 35th International Mathematical Olympiad in 1994 at Hong Kong (see the link IMO).
This sequence is increasing because there are only these two possibilities:
-> a(n+1) - a(n) = 1 if n has exactly two 1's in its binary representation (A018900);
-> a(n+1) - a(n) = 0 otherwise.
Consequence, for any positive integer m, a(x) = m has at least one solution (answer to the 1st Olympiad question).
Only when m = k*(k-1)/2 + 1 with k >= 2 (A000124 \ {1}), there exists only one n such that a(n) = m, and then n = 2^k+2 where k >= 2 (A052548 \ {3, 4}) (answer to the 2nd Olympiad question).

			a(2) = 0 because in {3, 4}, 3 = 11_2 and 4 = 100_2.
a(4) = 1 because in {5, 6, 7, 8, 9, 10} only 7 = 111_2 has 3 digits in its binary representation.
a(6) = 2 because in {7, 8, 9, 10, 11, 12}, there are 7 = 111_2 and 11 = 1011_2 that have 3 digits in their binary representation.

Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 10 and 92-93.

The IMO Compendium, Problem 3, 35th IMO 1994.
Index to sequences related to Olympiads.

Cf. A000120, A014311, A018900, A057168, A151774 (first differences).

a[n_] := Count[Range[n + 1, 2*n], ?(DigitCount[#, 2, 1] == 3 &)]; Array[a, 100] (* _Amiram Eldar, Dec 28 2020 *)

a(n) = sum(k=n+1, 2*n, hammingweight(k) == 3); \\ Michel Marcus, Dec 28 2020

first(n) = {my(res = vector(n), t = 0); for(i = 1, n, res[i] = t; if(hammingweight(i) == 2, t++)); res} \\ David A. Corneth, Dec 29 2020

def a(n): return sum(bin(k)[2:].count("1")==3 for k in range(n+1, 2*n+1))
print([a(n) for n in range(1, 68)]) # Michael S. Branicky, Dec 28 2020

def A340068(n): return sum(1 for k in range(n) if k.bit_count()==2) # Chai Wah Wu, Mar 11 2025

a(2^k+2) = k*(k-1)/2 + 1 for k >= 2.

More terms from David A. Corneth, Dec 28 2020

A361074 Sum of the j-th number with binary weight n-j+1 over all j in [n].

Original entry on oeis.org

0, 1, 5, 16, 40, 92, 193, 401, 812, 1632, 3261, 6526, 13030, 26049, 52013, 103974, 207797, 415496, 830636, 1661086, 3321498, 6642591, 13283920, 26567121, 53131653, 106261922, 212518857, 425034976, 850060303, 1700115399, 3400211408, 6800412866, 13600787296

Offset: 0

Alois P. Heinz, Mar 01 2023

			a(0) = 0 (empty sum).
a(1) = 1 = 1_2.
a(2) = 5 = 2 + 3 = 10_2 + 11_2.
a(3) = 16 = 4 + 5 + 7 = 100_2 + 101_2 + 111_2.
a(4) = 40 = 8 + 6 + 11 + 15 = 1000_2 + 110_2 + 1011_2 + 1111_2.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Antidiagonal sums of A066884 or of A067576.

Cf. A000120, A057168.

b:= proc(i, j) option remember; uses Bits: local c, l, k;
      if j=1 then 2^i-1
    else c, l:= 0, [Split(b(i, j-1))[], 0];
         for k while l[k]<>1 or l[k+1]<>0 do c:=c+l[k] od;
         Join([1$c, 0$k-c, 1, l[k+2..-1][]])
      fi
    end:
a:= n-> add(b(j, n-j+1), j=1..n):
seq(a(n), n=0..32);

a(n) = Sum_{j=1..n} A066884(j,n-j+1) = Sum_{j=1..n} A067576(j,n-j+1).

Conjecture: a(n) ~ 19 * 2^n / 6. - Vaclav Kotesovec, Mar 04 2023

A057169 Least integer with the same nonzero decimal digits as n and one more 0 digit.

Original entry on oeis.org

10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 200, 102, 202, 203, 204, 205, 206, 207, 208, 209, 300, 103, 203, 303, 304, 305, 306, 307, 308, 309, 400, 104, 204, 304, 404, 405, 406, 407, 408, 409, 500, 105

Offset: 1

N. J. A. Sloane, Sep 15 2000

Robert Israel, Table of n, a(n) for n = 1..10000

Decimal analog of A057168. Cf. A004185.

f:= proc(n) local L,m,p;
L:= convert(n,base,10);
m:= nops(L);
L:= sort(subs(0=NULL,L));
p:= nops(L);
10^m*L[1]+add(L[j]*10^(p-j),j=2..p)
end proc:
map(f, [$1..100]); # Robert Israel, May 06 2018

Definition corrected by Robert Israel, May 06 2018

A343604 a(n) is the least number > n with the same sum of balanced ternary digits as n.

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Apr 22 2021

This sequence can be extended to negative indexes by setting a(-n) = -A343605(n) for any n > 0.

			The first terms, in base 10 and in balanced ternary (where T denotes the digit -1), alongside A065363(n), are:
  n   a(n)  bter(n)  bter(a(n))  A065363(n)
  --  ----  -------  ----------  ----------
   0     2        0          1T           0
   1     3        1          10           1
   2     6       1T         1T0           0
   3     7       10         1T1           1
   4    10       11         101           2
   5    15      1TT        1TT0          -1
   6     8      1T0         10T           0
   7     9      1T1         100           1
   8    16      10T        1TT1           0
   9    11      100         11T           1
  10    12      101         110           2
  11    19      11T        1T01           1
  12    22      110        1T11           2

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Cf. A057168, A065363, A174658, A228915, A319021, A343605.

A065363(n) = { my (v=0, d); while (n, v+=d=centerlift(Mod(n,3)); n=(n-d)\3); v }
a(n) = my (s=A065363(n)); for (k=n+1, oo, if (s==A065363(k), return (k)))

a(9*n) = 9*n + 2.

a(A174658(n)) = A174658(n+1).

cp's OEIS Frontend

A263017 n is the a(n)-th positive integer having its binary weight.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Perl

Python

Formula

A140977 a(n) is the smallest integer > n that has the same number of (nonleading) zeros in its binary representation as n has.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A171942 Forward van Eck transform of A000120.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

A243109 a(n) is the largest number smaller than n and having the same Hamming weight as n, or n if no such number exist.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A295827 a(n) = least odd k > 1 such that n and n*k have the same Hamming weight, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A319021 Next larger integer with same sum of digits in base 3 as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.

Views