%I #88 Apr 26 2024 03:31:06

%S 0,0,1,0,1,2,3,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,

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

%U 26,27,28,29,30,31,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

%N Distance to largest power of 2 less than or equal to n; write n in binary, change the first digit to zero, and convert back to decimal.

%C Triangle read by rows in which row n lists the first 2^n nonnegative integers (A001477), n >= 0. Right border gives A000225. Row sums give A006516. See example. - _Omar E. Pol_, Oct 17 2013

%C Without the initial zero also: zeroless numbers in base 3 (A032924: 1, 2, 11, 12, 21, ...), ternary digits decreased by 1 and read as binary. - _M. F. Hasler_, Jun 22 2020

%H Reinhard Zumkeller, <a href="/A053645/b053645.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, preprint, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197 (see Ex. 24).

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = n - 2^A000523(n).

%F G.f.: 1/(1-x) * ((2x-1)/(1-x) + Sum_{k>=1} 2^(k-1)*x^2^k). - _Ralf Stephan_, Apr 18 2003

%F a(n) = (A006257(n)-1)/2. - _N. J. A. Sloane_, May 16 2003

%F a(1) = 0, a(2n) = 2a(n), a(2n+1) = 2a(n) + 1. - _N. J. A. Sloane_, Sep 13 2003

%F a(n) = A062050(n) - 1. - _N. J. A. Sloane_, Jun 12 2004

%F a(A004760(n+1)) = n. - _Reinhard Zumkeller_, May 20 2009

%F a(n) = f(n-1,1) with f(n,m) = if n < m then n else f(n-m,2*m). - _Reinhard Zumkeller_, May 20 2009

%F Conjecture: a(n) = (1 - A036987(n-1))*(1 + a(n-1)) for n > 1 with a(1) = 0. - _Mikhail Kurkov_, Jul 16 2019

%e From _Omar E. Pol_, Oct 17 2013: (Start)

%e Written as an irregular triangle the sequence begins:

%e 0;

%e 0,1;

%e 0,1,2,3;

%e 0,1,2,3,4,5,6,7;

%e 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15;

%e ...

%e (End)

%p seq(n - 2^ilog2(n), n=1..1000); # _Robert Israel_, Dec 23 2015

%t Table[n - 2^Floor[Log2[n]], {n, 100}] (* _IWABUCHI Yu(u)ki_, May 25 2017 *)

%t Table[FromDigits[Rest[IntegerDigits[n, 2]], 2], {n, 100}] (* _IWABUCHI Yu(u)ki_, May 25 2017 *)

%o (Haskell)

%o a053645 1 = 0

%o a053645 n = 2 * a053645 n' + b where (n', b) = divMod n 2

%o -- _Reinhard Zumkeller_, Aug 28 2014

%o a053645_list = concatMap (0 `enumFromTo`) a000225_list

%o -- _Reinhard Zumkeller_, Feb 04 2013, Mar 23 2012

%o (PARI) a(n)=n-2^(#binary(n)-1) \\ _Charles R Greathouse IV_, Sep 02 2015

%o (Magma) [n - 2^Ilog2(n): n in [1..70]]; // _Vincenzo Librandi_, Jul 18 2019

%o (Python)

%o def a(n): return n - 2**(n.bit_length()-1)

%o print([a(n) for n in range(1, 85)]) # _Michael S. Branicky_, Jul 03 2021

%o (Python)

%o def A053645(n): return n&(1<<n.bit_length()-1)-1 # _Chai Wah Wu_, Jan 22 2023

%Y Cf. A000225, A000523, A002262, A004760, A006257, A006516, A030308, A036987, A053644, A062050, A083741, A160588.

%K nonn,base,easy

%O 1,6

%A _Henry Bottomley_, Mar 22 2000