A080080 -id:A080080 - cp's OEIS frontend

A080079 Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.

1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 32, 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, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47

Offset: 1

Reinhard Zumkeller, Jan 26 2003

T(n,k) < T(n,a(n)) = A070940(n) for 1 <= k < a(n) and T(n,k) <= T(n,a(n)) for a(n) <= k <= n, where T is defined as in A080080.

a(n) gives the distance from n to the nearest 2^t > n. - Ctibor O. Zizka, Apr 09 2020

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

Cf. A327489, A004755, A062383, A080080, A240769, A006257.

a080079 n = (length $ takeWhile (< a070940 n) (a080080_row n)) + 1
-- Reinhard Zumkeller, Apr 22 2013

[-n+2*2^Floor(Log(n)/Log(2)): n in [1..80]]; // Vincenzo Librandi, Dec 01 2016

# Alois P. Heinz observes in A327489:
A080079 := n -> 1 + Bits:-Nor(n, n):
# Likewise:
A080079 := n -> 1 + Bits:-Nand(n, n):
seq(A080079(n), n=1..81); # Peter Luschny, Sep 23 2019

Flatten@Table[Nest[Most[RotateRight[#]] &, Range[n], n - 1], {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[FromDigits[(IntegerDigits[n, 2] /. {0 -> 1, 1 -> 0}), 2] +
1, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1] + 1, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[2 2^Floor[Log[2, n]] - n, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Flatten@Table[Reverse@Range[2^n], {n, 0, 4}] (* Birkas Gyorgy, Feb 07 2011 *)

def A080079(n): return (1 << n.bit_length())-n # Chai Wah Wu, Jun 30 2022

From Benoit Cloitre, Feb 22 2003: (Start)
a(n) = A004755(n) - 2*n.
a(n) = -n + 2*2^floor(log(n)/log(2)). (End)
From Ralf Stephan, Jun 02 2003: (Start)
a(n) = n iff n = 2^k, otherwise a(n) = A035327(n-1).
a(n) = A062383(n) - n. (End)
a(0) = 0, a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)-1 + 2*[n==0]. - Ralf Stephan, Jan 04 2004
a(n) = A240769(n,1); A240769(n, a(n)) = 1. - Reinhard Zumkeller, Apr 13 2014
a(n) = n + 1 - A006257(n). - Reinhard Zumkeller, Apr 14 2014

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

A050600 Recursion counts for summation table A003056 with formula a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 22 1999

Count the summation table A003056 with recursive formula based on identity A+B = (A XOR B)+ 2*(A AND B) given by Schroeppel and then this table gives the number of recursion steps to get the final result.

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

Reinhard Zumkeller, Rows n = 0..127 of triangle, flattened
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel)
Index entries for sequences related to binary expansion of n

Column 1: A001511, column 2: A050603, column 3: A050604.
Cf. A050601, A050602, A003056, A048720 (for the Maple implementation of trinv and XORnos, ANDnos)
Cf. A080080.

import Data.Bits (xor, (.&.), shiftL)
a050600 n k = adder 0 (n - k) k where
   adder :: Int -> Int -> Int -> Int
   adder c u 0 = c
   adder c u v = adder (c + 1) (u `xor` v) (shiftL (u .&. v) 1)
a050600_row n = map (a050600 n) $ reverse [0..n]
a050600_tabl = map a050600_row [0..]
-- Reinhard Zumkeller, Aug 02 2014

add1c := proc(a,b) option remember; if(0 = b) then RETURN(0); else RETURN(1+add_c(XORnos(a,b),2*ANDnos(a,b))); fi; end;

trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
add1c[a_, b_] := add1c[a, b] = If[b == 0, 0, 1 + add1c[BitXor[a, b], 2*BitAnd[a, b]]];
a[n_] := add1c[n - (trinv[n]*(trinv[n] - 1))/2, (trinv[n] - 1)* ((1/2)*trinv[n] + 1) - n];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 21 2021, after Maple code *)

a(n) -> add1c( (n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n) )

cp's OEIS Frontend

A080079 Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

R

Formula

Extensions

A050600 Recursion counts for summation table A003056 with formula a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula