A062383 - OEIS

%I #111 Jan 29 2025 19:36:37

%S 1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32,32,32,32,32,32,32,32,32,

%T 32,32,32,32,32,32,32,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,

%U 64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,128,128,128,128,128,128

%N a(0) = 1: for n>0, a(n) = 2^floor(log_2(n)+1) or a(n) = 2*a(floor(n/2)).

%C Informally, write down 1 followed by 2^k 2^(k-1) times, for k = 1,2,3,4,... These are the denominators of the binary van der Corput sequence (see A030101 for the numerators). - _N. J. A. Sloane_, Dec 01 2019

%C a(n) is the denominator of the form 2^k needed to make the ratio (2n-1)/2^k lie in the interval [1-2], i.e. such ratios are 1/1, 3/2, 5/4, 7/4, 9/8, 11/8, 13/8, 15/8, 17/16, 19/16, 21/16, ... where the numerators are A005408 (The odd numbers).

%C Let A_n be the upper triangular matrix in the group GL(n,2) that has zero entries below the diagonal and 1 elsewhere. For example for n=4 the matrix is / 1,1,1,1 / 0,1,1,1 / 0,0,1,1 / 0,0,0,1 /. The order of this matrix as an element of GL(n,2) is a(n-1). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 14 2001

%C A006257(n)/a(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

%C a(n) = maximum of row n+1 in A240769. - _Reinhard Zumkeller_, Apr 13 2014

%C This is the discriminator sequence for the odious numbers. - _N. J. A. Sloane_, May 10 2016

%H Harry J. Smith, <a href="/A062383/b062383.txt">Table of n, a(n) for n = 0..1000</a>

%H L. K. Arnold, S. J. Benkoski and B. J. McCabe, <a href="http://www.jstor.org/stable/2323651">The discriminator (a simple application of Bertrand's postulate)</a>. Amer. Math. Monthly 92 (1985), 275-277.

%H Sajed Haque, Chapter 2.6.1 of <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/12234/Haque_Sajed.pdf">Discriminators of Integer Sequences</a>, 2017, See p. 33.

%H S. Haque and J. Shallit, <a href="http://arxiv.org/abs/1605.00092">Discriminators and k-regular sequences</a>, arXiv:1605.00092 [cs.DM], 2016.

%H Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625, Dec 08, 2020

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%F a(1) = 1 and a(n+1) = a(n)*ceiling(n/a(n)). - _Benoit Cloitre_, Aug 17 2002

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

%F a(n) = A142151(2*n)/2 + 1. - _Reinhard Zumkeller_, Jul 15 2008

%F log(a(n))/log(2) = A029837(n+1). - _Johannes W. Meijer_, Jul 06 2009

%F a(n+1) = a(n) + A099894(n). - _Reinhard Zumkeller_, Aug 06 2009

%F a(n) = A264619(n) - A264618(n). - _Reinhard Zumkeller_, Dec 01 2015

%F a(n) is the smallest power of 2 > n. - _Chai Wah Wu_, Nov 04 2016

%F a(n) = 2^ceiling(log_2(n+1)). - _M. F. Hasler_, Sep 20 2017

%p [seq(2^(floor_log_2(j)+1),j=0..127)]; or [seq(coerce1st_octave((2*j)+1),j=0..127)]; or [seq(a(j),j=0..127)];

%p coerce1st_octave := proc(r) option remember; if(r < 1) then coerce1st_octave(2*r); else if(r >= 2) then coerce1st_octave(r/2); else (r); fi; fi; end;

%p A062383 := proc(n)

%p     option remember;

%p     if n = 0 then

%p         1 ;

%p     else

%p         2*procname(floor(n/2));

%p     end if;

%p end proc:

%p A062383 := n -> 1 + Bits:-Iff(n, n):

%p seq(A062383(n), n=0..69); # _Peter Luschny_, Sep 23 2019

%t a[n_] := a[n] = 2 a[n/2 // Floor]; a[0] = 1; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Mar 04 2016 *)

%t Table[2^Floor[Log2[n] + 1], {n, 0, 20}] (* _Eric W. Weisstein_, Nov 17 2017 *)

%t 2^Floor[Log2[Range[0, 20]] + 1] (* _Eric W. Weisstein_, Nov 17 2017 *)

%t 2^BitLength[Range[0, 100]] (* _Paolo Xausa_, Jan 29 2025 *)

%o (PARI) { a=1; for (n=0, 1000, write("b062383.txt", n, " ", a*=ceil((n + 1)/a)) ) } \\ _Harry J. Smith_, Aug 06 2009

%o (PARI) a(n)=1<<(log(2*n+1)\log(2)) \\ _Charles R Greathouse IV_, Dec 08 2011

%o (Haskell)

%o import Data.List (transpose)

%o a062383 n = a062383_list !! n

%o a062383_list = 1 : zs where

%o    zs = 2 : (map (* 2) $ concat $ transpose [zs, zs])

%o -- _Reinhard Zumkeller_, Aug 27 2014, Mar 13 2014

%o (Magma) [2^Floor(Log(2,2*n+1)): n in [0..70]]; // _Bruno Berselli_, Mar 04 2016

%o (Python)

%o def A062383(n): return 1 << n.bit_length() # _Chai Wah Wu_, Jun 30 2022

%Y Apart from the initial term, A062383[n] = 2* A053644[n]. MASKTRANSi(A062383) seems to give a signed form of A038712. (See identities at A053644). floor_log_2 given in A054429.

%Y Equals A003817(n)+1. Cf. A002884.

%Y Bisection of A065285. Cf. A076877.

%Y Equals for n>=1 the r(n) sequence of A160464. - _Johannes W. Meijer_, May 24 2009

%Y Equals the r(n) sequence of A162440 for n>=1. - _Johannes W. Meijer_, Jul 06 2009

%Y Cf. A030101, A264618, A264619.

%Y Discriminator of the odious numbers (A000069). - _Jeffrey Shallit_, May 08 2016

%K nonn,frac,easy

%O 0,2

%A _Antti Karttunen_, Jun 19 2001