A080079 -id:A080079 - cp's OEIS frontend

A355435 Lexicographically earliest sequence of distinct positive integers such that for any n > 1, a(n) is a multiple of a(A080079(n-1)).

1, 2, 4, 3, 6, 8, 10, 5, 15, 20, 16, 12, 9, 24, 14, 7, 21, 28, 48, 18, 36, 32, 40, 30, 25, 50, 56, 42, 27, 44, 22, 11, 33, 66, 88, 54, 84, 112, 100, 75, 60, 80, 64, 72, 90, 96, 140, 63, 35, 70, 120, 45, 108, 128, 160, 105, 55, 110, 104, 78, 39, 52, 26, 13

Offset: 1

Rémy Sigrist, Jul 02 2022

This sequence is a permutation of the positive integers with inverse A355436.
The construction of this sequence is similar to that of A269838.
This sequence can also be seen as an irregular table:
- with row lengths given by A011782,
- with initial row (1),
- given the first k+1 rows (with globally 2^k terms), the next row contains a multiple of a(2^k), followed by a multiple of a(2^k-1), ..., followed by a multiple of a(1).

			As an irregular table, the first rows are:
    [1]
    [2]
    [4, 3]
    [6, 8, 10, 5]
    [15, 20, 16, 12, 9, 24, 14, 7]
    [21, 28, 48, 18, 36, 32, 40, 30, 25, 50, 56, 42, 27, 44, 22, 11]
.
The first terms are:
  n   a(n)  A080079(n-1)  a(A080079(n-1))
  --  ----  ------------  ---------------
   1     1  N/A           N/A
   2     2             1                1
   3     4             2                2
   4     3             1                1
   5     6             4                3
   6     8             3                4
   7    10             2                2
   8     5             1                1
   9    15             8                5
  10    20             7               10
  11    16             6                8
  12    12             5                6
  13     9             4                3
  14    24             3                4
  15    14             2                2
  16     7             1                1

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A011782, A080079, A269838, A355436 (inverse).

PARI
```
See Links section.
```

a(2^n) = prime(n) for any n > 0 (where prime(n) denotes the n-th prime number).

A337909 Distinct terms of A080079 in the order in which they appear.

Original entry on oeis.org

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

Offset: 1

Lorenzo Sauras Altuzarra, Sep 29 2020

nonn

This sequence is a permutation of the positive integers.

The cardinality of {2^k, ..., (2^k - 0^k)/2 + 1} is A011782(k).

			(2^0, ..., (2^0 - 0^0)/2 + 1) = (1),
(2^1, ..., (2^1 - 0^1)/2 + 1) = (2),
(2^2, ..., (2^2 - 0^2)/2 + 1) = (4, 3),
(2^3, ..., (2^3 - 0^3)/2 + 1) = (8, 7, 6, 5)...

Index entries for sequences that are permutations of the natural numbers

Cf. A004761, A011782, A053644, A054429, A080079, A280510.

{1}~Join~Array[3*2^(IntegerLength[# - 1, 2] - 1) - # + 1 &, 64, 2] (* Michael De Vlieger, Oct 05 2020 *)

a(n) = if(n--, 3<Kevin Ryde, Sep 29 2020

a(1) = 1 and a(n) = A080079(n - 1 + 2^floor(log_2(n - 1))) if n > 1.
a(n) = A080079(A004761(n+1)).
From Kevin Ryde, Sep 29 2020: (Start)
a(n) = 3*A053644(n-1) - (n-1), if n > 1.
a(n) = A054429(n-1) + 1, if n > 1.
a(n) = A280510(n) - n + 1, if n > 1. (End)

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

Offset: 0

N. J. A. Sloane

Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.
A version of the children's game "One potato, two potato, ...".
a(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010
By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2.  This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013
Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013
For n > 0: a(n) = n + 1 - A080079(n). - Reinhard Zumkeller, Apr 14 2014
In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016
In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2*A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020

			From _Omar E. Pol_, Jun 09 2009: (Start)
Written as an irregular triangle the sequence begins:
  0;
  1;
  1,3;
  1,3,5,7;
  1,3,5,7,9,11,13,15;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,
   43,45,47,49,51,53,55,57,59,61,63;
...
(End)
From _Omar E. Pol_, Nov 03 2018: (Start)
An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:
   n   a(n)       Diagram
   0    0     _
   1    1    |_|_ _
   2    1      |_| |
   3    3      |_ _|_ _ _ _
   4    1          |_| | | |
   5    3          |_ _| | |
   6    5          |_ _ _| |
   7    7          |_ _ _ _|
(End)

Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.
M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

Iain Fox, Table of n, a(n) for n = 0..100000 (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniel Erman and Brady Haran, The Josephus Problem, Numberphile video (2016)
Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
Yuri Nikolayevsky and Ioannis Tsartsaflis, Cohomology of N-graded Lie algebras of maximal class over Z_2, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus problem
Index entries for sequences related to the Josephus Problem

Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.
Second column, and main diagonal, of triangle A032434.
Cf. A181281 (with s=5), A054995 (with s=3).
Column k=2 of A360099.

Require Import ZArith.
Fixpoint a (n : positive) : Z :=
match n with
| xH => 1
| xI n' => (2*(a n') + 1)%Z
| xO n' => (2*(a n') - 1)%Z
end.
(* Stefan Haan, Aug 27 2023 *)

a006257 n = a006257_list !! n
a006257_list =
   0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])
-- Reinhard Zumkeller, Oct 06 2011

[0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016

a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
seq(a(i),i=0..100); # Paul Weisenhorn, Oct 10 2010; corrected by Robert Israel, Jan 13 2016
A006257 := proc(n)
    convert(n,base,2) ;
    ListTools[Rotate](%,-1) ;
    add( op(i,%)*2^(i-1),i=1..nops(%)) ;
end proc: # R. J. Mathar, May 20 2016
A006257 := n -> 2*n  - Bits:-Iff(n, n):
seq(A006257(n), n=0..78); # Peter Luschny, Sep 24 2019

Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *)
Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *)
m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)

a(n)=sum(k=1,n,if(bitxor(n,k)Paul D. Hanna

a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016

import math
def A006257(n):
     return 0 if n==0 else 2*(n-2**int(math.log(n,2)))+1 # Indranil Ghosh, Jan 11 2017

def A006257(n): return bool(n&(m:=1<Chai Wah Wu, Jan 22 2023
(C#)
static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021

To get a(n), write n in binary, rotate left 1 place.
a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun, Jul 11 2001. [Here "msb" = "most significant bit", A053644.]
G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006
a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006
a(n) = n - A035327(n). - K. Spage, Oct 22 2009
a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010
a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013
a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019
For n > 0: a(n) = 2 * A062050(n) - 1. - Frank Hollstein, Oct 25 2021

More terms from Robert G. Wilson v, Sep 21 2003

A035327 Write n in binary, interchange 0's and 1's, convert back to decimal.

Original entry on oeis.org

1, 0, 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46

Offset: 0

N. J. A. Sloane

For n>0: largest m<=n such that no carry occurs when adding m to n in binary arithmetic: A003817(n+1) = a(n) + n = a(n) XOR n. - Reinhard Zumkeller, Nov 14 2009
a(0) could be considered to be 0 (it was set so from 2004 to 2008) if the binary representation of zero was chosen to be the empty string. - Jason Kimberley, Sep 19 2011
For n > 0: A240857(n,a(n)) = 0. - Reinhard Zumkeller, Apr 14 2014
This is a base-2 analog of A048379. Another variant, without converting back to decimal, is given in A256078. - M. F. Hasler, Mar 22 2015
For n >= 2, a(n) is the least nonnegative k that must be added to n+1 to make a power of 2. Hence in a single-elimination tennis tournament with n entrants, a(n-1) is the number of players given a bye in round one, so that the number of players remaining at the start of round two is a power of 2. For example, if 39 players register, a(38)=25 players receive a round-one bye leaving 14 to play, so that round two will have 25+(14/2)=32 players. - Mathew Englander, Jan 20 2024

			8 = 1000 -> 0111 = 111 = 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n
Index entries for sequences related to the Josephus Problem

a(n) = A003817(n) - n, for n>0.
Cf. A080079, A087734, A167831, A167877, A007088, A061601, A171960, A010078, A000225, A006257 (Josephus problem).
Cf. A240857.
Cf. A048379, A256078.

a035327 n = if n <= 1 then 1 - n else 2 * a035327 n' + 1 - b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014

using IntegerSequences
A035327List(len) = [Bits("NAND", n, n) for n in 0:len]
println(A035327List(100))  # Peter Luschny, Sep 25 2021

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

seq(2^(1 + ilog2(max(n, 1))) - 1 - n, n = 0..81); # Emeric Deutsch, Oct 19 2008
A035327 := n -> `if`(n=0, 1, Bits:-Nand(n, n)):
seq(A035327(n), n=0..81); # Peter Luschny, Sep 23 2019

Table[BaseForm[FromDigits[(IntegerDigits[i, 2]/.{0->1, 1->0}), 2], 10], {i, 0, 90}]
Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1], {n, 100}] (* Alonso del Arte, Jan 14 2006 *)
Join[{1},Table[2^BitLength[n]-n-1,{n,100}]] (* Paolo Xausa, Oct 13 2023 *)
Table[FromDigits[IntegerDigits[n,2]/.{0->1,1->0},2],{n,0,90}] (* Harvey P. Dale, May 03 2025 *)

a(n)=sum(k=1,n,if(bitxor(n,k)>n,1,0)) \\ Paul D. Hanna, Jan 21 2006

a(n) = bitxor(n, 2^(1+logint(max(n,1), 2))-1) \\ Rémy Sigrist, Jan 04 2019

a(n)=if(n, bitneg(n, exponent(n)+1), 1) \\ Charles R Greathouse IV, Apr 13 2020

def a(n): return int(''.join('1' if i == '0' else '0' for i in bin(n)[2:]), 2) # Indranil Ghosh, Apr 29 2017

def a(n): return 1 if n == 0 else n^((1 << n.bit_length()) - 1)
print([a(n) for n in range(100)]) # Michael S. Branicky, Sep 28 2021

def A035327(n): return (~n)^(-1<Chai Wah Wu, Dec 20 2022

def a(n):
    if n == 0:
        return 1
    return sum([(1 - b) << s for (s, b) in enumerate(n.bits())])
[a(n) for n in srange(82)]  # Peter Luschny, Aug 31 2019

a(n) = 2^k - n - 1, where 2^(k-1) <= n < 2^k.
a(n+1) = (a(n)+n) mod (n+1); a(0) = 1. - Reinhard Zumkeller, Jul 22 2002
G.f.: 1 + 1/(1-x)*Sum_{k>=0} 2^k*x^2^(k+1)/(1+x^2^k). - Ralf Stephan, May 06 2003
a(0) = 0, a(2n+1) = 2*a(n), a(2n) = 2*a(n) + 1. - Philippe Deléham, Feb 29 2004
a(n) = number of positive integers k < n such that n XOR k > n. a(n) = n - A006257(n). - Paul D. Hanna, Jan 21 2006
a(n) = 2^{1+floor(log[2](n))}-n-1 for n>=1; a(0)=1. - Emeric Deutsch, Oct 19 2008
a(n) = if n<2 then 1 - n else 2*a(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Jan 20 2010
a(n) = abs(2*A053644(n) - n - 1). - Mathew Englander, Jan 22 2024

More terms from Vit Planocka (planocka(AT)mistral.cz), Feb 01 2003
a(0) corrected by Paolo P. Lava, Oct 22 2007
Definition completed by M. F. Hasler, Mar 22 2015

A004755 Binary expansion starts 11.

Original entry on oeis.org

3, 6, 7, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122

Offset: 1

N. J. A. Sloane

a(n) is the smallest value > a(n-1) (or > 1 for n=1) for which A001511(a(n)) = A001511(n). - Franklin T. Adams-Watters, Oct 23 2006

			12 in binary is 1100, so 12 is in the sequence.

Kenny Lau, Table of n, a(n) for n = 1..16383 (first 1023 terms from T. D. Noe)
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Equals union of A079946 and A080565.
Cf. A004754 (10), A004756 (100), A004757 (101), A004758 (110), A004759 (111).
Cf. A004760, A053644, A062050, A076877.

import Data.List (transpose)
a004755 n = a004755_list !! (n-1)
a004755_list = 3 : concat (transpose [zs, map (+ 1) zs])
                   where zs = map (* 2) a004755_list
-- Reinhard Zumkeller, Dec 04 2015

a:= proc(n) n+2*2^floor(log(n)/log(2)) end: seq(a(n),n=1..60); # Muniru A Asiru, Oct 16 2018

Flatten[Table[FromDigits[#,2]&/@(Join[{1,1},#]&/@Tuples[{0,1},n]),{n,0,5}]] (* Harvey P. Dale, Feb 05 2015 *)

PARI
```
a(n)=n+2*2^floor(log(n)/log(2))
```

is(n)=n>2 && binary(n)[2] \\ Charles R Greathouse IV, Sep 23 2012

f = open('b004755.txt', 'w')
lo = 3
hi = 4
i = 1
while i<16384:
    for x in range(lo,hi):
        f.write(str(i)+" "+str(x)+"\n")
        i += 1
    lo <<= 1
    hi <<= 1
# Kenny Lau, Jul 05 2016

def A004755(n): return n+(1<Chai Wah Wu, Jul 13 2022

a(2n) = 2*a(n), a(2n+1) = 2*a(n) + 1 + 2*[n==0].
a(n) = n + 2 * 2^floor(log_2(n)) = A004754(n) + A053644(n).
a(n) = 2n + A080079(n). - Benoit Cloitre, Feb 22 2003
G.f.: (1/(1+x)) * (1 + Sum_{k>=0, t=x^2^k} 2^k*(2t+t^2)/(1+t)).
a(n) = n + 2^(floor(log_2(n)) + 1) = n + A062383(n). - Franklin T. Adams-Watters, Oct 23 2006
a(2^m+k) = 2^(m+1) + 2^m + k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016

Edited by Ralf Stephan, Oct 12 2003

A070940 Number of digits that must be counted from left to right to reach the last 1 in the binary representation of n.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 2, 4, 3, 4, 1, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 1, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 2, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 1, 7, 6, 7, 5, 7, 6, 7, 4, 7, 6, 7, 5, 7, 6, 7, 3, 7, 6, 7, 5, 7, 6, 7, 4, 7, 6, 7, 5, 7

Offset: 1

N. J. A. Sloane, May 18 2002

Length of longest carry sequence when adding numbers <= n to n in binary representation: a(n) = T(n, A080079(n)) and T(n,k) <= a(n) for 1 <= k <= n, with T defined as in A080080. - Reinhard Zumkeller, Jan 26 2003
a(n+1) is the number of distinct values of gcd(2^n, binomial(n,j)) (or, equivalently, A007814(binomial(n,j))) arising for j=0..n-1. Proof using Kummer's Theorem given by Marc Schwartz. - Labos Elemer, Apr 23 2003
E.g., n=10: 10th row of Pascal's triangle = {1,10,45,120,210,252,210,120,45,10,1}, largest powers of 2 dividing binomial coefficients is: {1,2,1,8,2,4,2,8,1,2,1}; including distinct powers of 2, thus a(10)=4. If m=-1+2^k, i.e., m=0,1,3,7,15,31,... then a(m)=1. This corresponds to "odd rows" of Pascal's triangle. - Labos Elemer
Smallest x > 0 for which a(x)=n equals 2^n. - Labos Elemer
a(n) <= A070939(n), a(n) = A070939(n) iff n is odd, where A070939(n) = floor(log_2(n)) + 1. - Reinhard Zumkeller, Jan 26 2003
Can be regarded as a table with row n having 2^(n-1) columns, with odd columns repeating the previous row, and even columns containing the row number. - Franklin T. Adams-Watters, Nov 08 2011
It appears that a(n) is the greatest number in a periodicity equivalence class defined at A269570; e.g., the 5 classes for n = 35 are (1, 1, 2, 2, 6), (1, 1, 1, 1, 4, 2, 2), (3), (1, 3), (1, 2); in these the greatest number is 6, so that a(35) = 6. - Clark Kimberling, Mar 01 2016
Number of binary digits of the largest odd factor of n. - Andres Cicuttin, May 18 2017

			a(10)=3 is the number of digits that must be counted from left to right to reach the last 1 in 1010, the binary representation of 10.
The table starts:
  1
  1 2
  1 3 2 3
  1 4 3 4 2 4 3 4

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A070939, A001511. Differs from A002487 around 11th term.
Cf. A000005, A007318, A000079, A082907, A082908.
Bisections give A070941 and this sequence (again).
Cf. A002064 (row sums), A199570.

a070940 = maximum . a080080_row  -- Reinhard Zumkeller, Apr 22 2013

A070940 := n -> if n mod 2 = 0 then A070939(n)-A001511(n/2) else A070939(n); fi;

Table[Length[Union[Table[GCD[2^n, Binomial[n, j]], {j, 0, n}]]], {n, 0, 256}]
f[n_] := Position[ IntegerDigits[n, 2], 1][[ -1, 1]]; Table[ f[n], {n, 105}] (* Robert G. Wilson v, Dec 01 2004 *)
(* By exploiting the "positional" regularity of the sequence *)
b = {}; a = {1, 1};
Do[a = Riffle[a, j];
  b = AppendTo[b, a[[1 ;; Floor[Length[a]/2]]]] // Flatten, {j, 1, 10}];
Print[b[[1 ;; 100]]] (* Andres Cicuttin, May 18 2017 *)
(* By following the alternative definition "Number of binary digits of the largest integer odd factor of n" *)
c = Table[IntegerDigits[n/(2^IntegerExponent[n, 2]), 2] // Length , {n,
    2^10 - 1}];
Print[c[[1 ;; 100]]] (* Andres Cicuttin, May 18 2017 *)
lidn[n_]:=Module[{idn=IntegerDigits[n,2]},idn=If[Last[idn]==0,Flatten[ Most[ Split[ idn]]],idn];Length[idn]]; Array[lidn,100] (* Harvey P. Dale, Oct 18 2020 *)
Table[IntegerLength[FromDigits[Reverse[IntegerDigits[n,2]]]],{n,100}] (* Harvey P. Dale, Jan 26 2025 *)

def A070940(n):
    while n%2 == 0:
        n = n//2
    a = 0
    while n != 0:
        n, a = n//2, a+1
    return a
n = 0
while n < 100:
    n = n+1
    print(n,A070940(n)) # A.H.M. Smeets, Aug 19 2019

def A070940(n): return n.bit_length()-(~n&n-1).bit_length() # Chai Wah Wu, Jul 13 2022

blocklevel <- 7  # by choice
a <- 1
for(m in 0:blocklevel)
  for(k in 0:(2^m-1)){
    a[2^(m+1)+2*k  ] <-  a[2^m+k]
    a[2^(m+1)+2*k+1] <-  m + 2
}
a
# Yosu Yurramendi, Aug 08 2019

a(n) = floor(log_2(n)) - A007814(n) = A070939(n) - A007814(n).
a(n) = f(n, 1), f(n, k) = if n=1 then k else f(floor(n/2), k+(if k>1 then 1 else n mod 2)). - Reinhard Zumkeller, Feb 01 2003
G.f.: Sum_{k>=0} (t/(1-t^2)) * (1 + Sum_{L>=1} t^2^L), where t=x^2^k. - Ralf Stephan, Mar 15 2004
a(n) = A070939(A000265(n)). - Andres Cicuttin, May 19 2017
a(1) = 1 and for m >= 0, 0 <= k < 2^m, a(2^(m+1)+2*k) = a(2^m+k), a(2^(m+1)+2*k+1) = m+2. - Yosu Yurramendi, Aug 08 2019

Entry revised by Ralf Stephan, Nov 29 2004

A261693 Irregular triangle read by rows in which row n lists the positive odd numbers in decreasing order starting with 2^n - 1. T(0, 1) = 0 and T(n, k) for n >= 1, 1 <= k <= 2^(n-1).

Original entry on oeis.org

0, 1, 3, 1, 7, 5, 3, 1, 15, 13, 11, 9, 7, 5, 3, 1, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 127, 125, 123, 121, 119, 117, 115, 113, 111, 109, 107, 105, 103, 101, 99, 97, 95, 93

Offset: 0

Omar E. Pol, Sep 25 2015

Also the first differences of A261692.
Number of cells turned ON at n-th stage of the cellular automaton of A261692.
This irregular triangle A (instead of T) appears also in the linearization of the following product of Chebyshev T polynomials (A053120): PrT(n) := Product_{j=1..n} T(2^j, x)  = (1/2^(n-1))*Sum_{k=1..2^(n-1)} T(2*A(n, k), x), for n >= 1. Proof via 2*T(n, x)*T(m, x) = T(n+m, x) + T(|n-m|, x). - Wolfdieter Lang, Oct 26 2019

			With the terms written as an irregular triangle T in which row lengths are the terms of A011782 the sequence begins:
0;
1;
3, 1;
7, 5, 3, 1;
15, 13, 11, 9, 7, 5, 3, 1;
31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1;
...
-------------------------------------------------------------------------------
From _Wolfdieter Lang_, Oct 26 2019: (Start)
Chebyshev T(2^j)-products (the argument x is here omitted):
n = 1: T(2) = (2^0)*T(2*1),
n = 2: T(2)*T(4) = (1/2)*(T(2*3) + T(2*1)) = (T(6) + T(2))/2,
n = 3: T(2)*T(4)*T(8) =  (1/2^2)*(T(2*7) + T(2*5) + T(2*3) + T(2*1))
       = (T(14) + T(10) + T(6) + T(2))/4.
... (End)

Cf. A036563, A005408, A011782, A080079, A099375, A147582, A262617, A261692, A262621.

Column 1 is A000225. Row sums give A000302, n >= 1.

A261693 := n -> Bits:-Nor(2*n, 2*n):
seq(A261693(n), n=0..81); # Peter Luschny, Sep 23 2019

Table[Reverse[2 Range[2^(n - 1)] - 1], {n, 0, 7}] /. {} -> 0 // Flatten (* Michael De Vlieger, Oct 05 2015 *)

tabf(nn) = {for (n=0, nn, print1(n, ":"); for (k=1, 2^(n-2), print1(2^(n-1) - 2*k + 1, ", ");); print(););} \\ Michel Marcus, Oct 27 2015

T(n, k) = 2^n + 1 - 2*k, n >= 1, 1 <= k <= 2^(n-1), and T(0, 0) = 0.

As a sequence: a(n) = A262621(n)/4, n >= 1, and a(0) = 0.

Corrections by Wolfdieter Lang, Nov 15 2019

A080080 T(n,k) = length of longest carry sequence when adding k to n in binary representation, 1 <= k <= n (triangular array).

Original entry on oeis.org

1, 0, 1, 2, 1, 1, 0, 0, 0, 1, 1, 0, 3, 1, 1, 0, 2, 2, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 1, 0, 4, 1, 1, 0, 1, 1, 0, 0, 3, 3, 1, 1, 1, 2, 1, 1, 0, 4, 3, 3, 1, 2, 1, 1, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 4, 2, 2, 2, 2, 1, 1, 1, 3, 1, 1, 0, 3, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1

Offset: 1

Reinhard Zumkeller, Jan 26 2003

T(n,1) = A007814(n+1), T(n,n) = 1; for n>1: T(n,n-1) = A043545(n+1); T(n,k) <= A070940(n) = T(n, A080079(n)).

T(n,k) = A050600(n+k,k) - 1. - Reinhard Zumkeller, Aug 03 2014

			Triangle begins:
              1
            0   1
          2   1   1
        0   0   0   1
      1   0   3   1   1
    0   2   2   1   1   1
  3   2   2   1   2   1   1

Reinhard Zumkeller, Rows n=1..150 of triangle, flattened
Index entries for sequences related to binary expansion of n

Cf. A050600.

import Data.Bits (xor, (.&.), shiftL)
a080080 :: Int -> Int -> Int
a080080 n k = addc n k 0 where
   addc x y z | y == 0    = z - 1
              | otherwise = addc (x `xor` y) (shiftL (x .&. y) 1) (z + 1)
a080080_row n = map (a080080 n) [1..n]
a080080_tabl = map a080080_row [1..]
-- Reinhard Zumkeller, Apr 22 2013

A255748 Total number of ON states after n generations of cellular automaton based on triangles in a 60-degree wedge (see Comments lines for definition).

Original entry on oeis.org

1, 3, 4, 8, 11, 13, 14, 22, 29, 35, 40, 44, 47, 49, 50, 66, 81, 95, 108, 120, 131, 141, 150, 158, 165, 171, 176, 180, 183, 185, 186, 218, 249, 279, 308, 336, 363, 389, 414, 438, 461, 483, 504, 524, 543, 561, 578, 594, 609, 623, 636, 648, 659, 669, 678, 686, 693, 699, 704, 708, 711, 713, 714, 778, 841, 903, 964, 1024

Offset: 1

Omar E. Pol, Mar 30 2015

Also partial sums of A080079.
In order to construct the structure we use the following rules:
On the infinite triangular grid we are in a 60-degree wedge with the vertex located on top of the wedge.
The nearest triangular cell to the vertex remains OFF.
At stage 1, we turn ON the cell whose base is adjacent to the previous OFF cell.
At stage n, in the n-th level of the structure, we turn ON k cells connected by their vertices with their bases up, where k = A080079(n).
The cells turned ON remain ON forever.
The structure seems to grow into the holes of a virtual Sierpiński's triangle (see example).
Note that this is also the structure in every one of the six wedges of the structure of A256266.
A080079 gives the number of cells turned ON at n-th stage.

			Illustration of initial terms:
-----------------------------------------------------------
n   A080079(n)   a(n)                  Diagram
-----------------------------------------------------------
.                                        / \
1       1         1                     / T \
2       2         3                    / T T \
3       1         4                   /   T   \
4       4         8                  / T T T T \
5       3        11                 /   T T T   \
6       2        13                /     T T     \
7       1        14               /       T       \
8       8        22              / T T T T T T T T \
9       7        29             /   T T T T T T T   \
10      6        35            /     T T T T T T     \
11      5        40           /       T T T T T       \
12      4        44          /         T T T T         \
13      3        47         /           T T T           \
14      2        49        /             T T             \
15      1        50       /               T               \
...
For n = 15 after 15 generations there are 50 ON cells in the structure, so a(15) = 50.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 37.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A047999, A001316, A080079, A139250, A169779, A169788, A170905, A233970, A256256, A256266.

Accumulate@ Flatten@ Table[Range[2^n, 1, -1], {n, 0, 6}] (* Michael De Vlieger, Nov 03 2022 *)

a(n) = A256266(n)/6.

A256266 Total number of ON states after n generations of cellular automaton based on triangles (see Comments lines for definition).

Original entry on oeis.org

0, 6, 18, 24, 48, 66, 78, 84, 132, 174, 210, 240, 264, 282, 294, 300, 396, 486, 570, 648, 720, 786, 846, 900, 948, 990, 1026, 1056, 1080, 1098, 1110, 1116, 1308, 1494, 1674, 1848, 2016, 2178, 2334, 2484, 2628, 2766, 2898, 3024, 3144, 3258, 3366, 3468, 3564, 3654, 3738, 3816, 3888, 3954, 4014, 4068, 4116, 4158, 4194, 4224, 4248

Offset: 0

Omar E. Pol, Mar 20 2015

On the infinite triangular grid we start at stage 0 with a hexagon formed by six OFF cells, so a(0) = 0.
At stage 1, around the mentioned hexagon, six triangular cells connected by their vertices are turned ON forming a six-pointed star, so a(1) = 6.
We use the same rules as A255748 for every one of the six 60-degree wedges of the structure.
If n is a power of 2 minus 1 and n is greater than 2, then the structure looks like concentric six-pointed stars.
If n is a power of 2 and n is greater than 2, then the structure looks like a hexagon that contains concentric six-pointed stars.
Note that in every wedge the structure seems to grow into the holes of a virtual Sierpiński's triangle (see example).

			Illustration of the structure after 15 generations:
(Note that every circle should be replaced with a triangle.)
.
.                            O
.                           O O
.                          O O O
.                         O O O O
.                        O O O O O
.                       O O O O O O
.                      O O O O O O O
.                     O O O O O O O O
.    O O O O O O O O \       O       / O O O O O O O O
.     O O O O O O O   \     O O     /   O O O O O O O
.      O O O O O O     \   O O O   /     O O O O O O
.       O O O O O       \ O O O O /       O O O O O
.        O O O O O O O O \   O   / O O O O O O O O
.         O O O   O O O   \ O O /   O O O   O O O
.          O O     O O O O \ O / O O O O     O O
.           O       O   O O \ / O O   O       O
.            - - - - - - - -   - - - - - - - -
.           O       O   O O / \ O O   O       O
.          O O     O O O O / O \ O O O O     O O
.         O O O   O O O   / O O \   O O O   O O O
.        O O O O O O O O /   O   \ O O O O O O O O
.       O O O O O       / O O O O \       O O O O O
.      O O O O O O     /   O O O   \     O O O O O O
.     O O O O O O O   /     O O     \   O O O O O O O
.    O O O O O O O O /       O       \ O O O O O O O O
.                     O O O O O O O O
.                      O O O O O O O
.                       O O O O O O
.                        O O O O O
.                         O O O O
.                          O O O
.                           O O
.                            O
.
There are 300 ON cells, so a(15) = 300.

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 37.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A001316, A047999, A080079, A139250, A151723, A160120, A161330, A161644, A255748, A256256.

6*Join[{0}, Accumulate@ Flatten@ Table[Range[2^n, 1, -1], {n, 0, 5}]] (* Michael De Vlieger, Nov 03 2022 *)

a(n) = 6 * A255748(n), n >= 1.

cp's OEIS Frontend

A355435 Lexicographically earliest sequence of distinct positive integers such that for any n > 1, a(n) is a multiple of a(A080079(n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A337909 Distinct terms of A080079 in the order in which they appear.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A006257 Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Coq

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A035327 Write n in binary, interchange 0's and 1's, convert back to decimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

SageMath

Formula

Extensions

A004755 Binary expansion starts 11.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.