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

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, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, 128, 128

Offset: 0

Author

Antti Karttunen, Jun 19 2001

Keywords

• nonn
• frac
• easy

Comments

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

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).

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

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

a(n) = maximum of row n+1 in A240769. - Reinhard Zumkeller, Apr 13 2014

This is the discriminator sequence for the odious numbers. - N. J. A. Sloane, May 10 2016

From Jianing Song, Jul 05 2025: (Start)

a(n) is the period of {binomial(N,n) mod 2: N in Z}. For the general result, see A349593.

Since the modulus (2) is a prime, the remainder of binomial(N,n) is given by Lucas's theorem. (End)

Links

• Harry J. Smith, Table of n, a(n) for n = 0..1000
• L. K. Arnold, S. J. Benkoski and B. J. McCabe, The discriminator (a simple application of Bertrand's postulate). Amer. Math. Monthly 92 (1985), 275-277.
• Sajed Haque, Chapter 2.6.1 of Discriminators of Integer Sequences, 2017, See p. 33.
• S. Haque and J. Shallit, Discriminators and k-regular sequences, arXiv:1605.00092 [cs.DM], 2016.
• Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions
• Wikipedia, Lucas's theorem
• Index to divisibility sequences

Crossrefs

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

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

Bisection of A065285. Cf. A076877.

Equals for n>=1 the r(n) sequence of A160464. - Johannes W. Meijer, May 24 2009

Equals the r(n) sequence of A162440 for n>=1. - Johannes W. Meijer, Jul 06 2009

Cf. A030101, A264618, A264619.

Discriminator of the odious numbers (A000069). - Jeffrey Shallit, May 08 2016

Column 2 of A349593. A064235 (if offset 0), A385552, A385553, and A385554 are respectively columns 3, 5, 6, and 10.

Programs

Haskell

import Data.List (transpose)
a062383 n = a062383_list !! n
a062383_list = 1 : zs where
   zs = 2 : (map (* 2) $ concat $ transpose [zs, zs])
-- Reinhard Zumkeller, Aug 27 2014, Mar 13 2014

Magma

[2^Floor(Log(2,2*n+1)): n in [0..70]]; // Bruno Berselli, Mar 04 2016

Maple

[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)];
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;
A062383 := proc(n)
    option remember;
    if n = 0 then
        1 ;
    else
        2*procname(floor(n/2));
    end if;
end proc:
A062383 := n -> 1 + Bits:-Iff(n, n):
seq(A062383(n), n=0..69); # Peter Luschny, Sep 23 2019

Mathematica

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 *)
Table[2^Floor[Log2[n] + 1], {n, 0, 20}] (* Eric W. Weisstein, Nov 17 2017 *)
2^Floor[Log2[Range[0, 20]] + 1] (* Eric W. Weisstein, Nov 17 2017 *)
2^BitLength[Range[0, 100]] (* Paolo Xausa, Jan 29 2025 *)

PARI

{ a=1; for (n=0, 1000, write("b062383.txt", n, " ", a*=ceil((n + 1)/a)) ) } \\ Harry J. Smith, Aug 06 2009

PARI

a(n)=1<<(log(2*n+1)\log(2)) \\ Charles R Greathouse IV, Dec 08 2011

Python

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

Formula

a(1) = 1 and a(n+1) = a(n)*ceiling(n/a(n)). - Benoit Cloitre, Aug 17 2002

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

a(n) = A142151(2*n)/2 + 1. - Reinhard Zumkeller, Jul 15 2008

log(a(n))/log(2) = A029837(n+1). - Johannes W. Meijer, Jul 06 2009

a(n+1) = a(n) + A099894(n). - Reinhard Zumkeller, Aug 06 2009

a(n) = A264619(n) - A264618(n). - Reinhard Zumkeller, Dec 01 2015

a(n) is the smallest power of 2 > n. - Chai Wah Wu, Nov 04 2016

a(n) = 2^ceiling(log_2(n+1)). - M. F. Hasler, Sep 20 2017