A003817 a(0) = 0, a(n) = a(n-1) OR n.

0, 1, 3, 3, 7, 7, 7, 7, 15, 15, 15, 15, 15, 15, 15, 15, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63

Offset: 0

Author

Marc LeBrun

Keywords

• nonn
• base
• nice

Comments

Also, 0+1+2+...+n in lunar arithmetic in base 2 written in base 10. - N. J. A. Sloane, Oct 02 2010

For n>0: replace all 0's with 1's in binary representation of n. - Reinhard Zumkeller, Jul 14 2003

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 [From _Reinhard Zumkeller_, Nov 14 2009]
• D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions
• Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
• Reinhard Zumkeller, Logical Convolutions
• Index entries for sequences related to dismal (or lunar) arithmetic

Crossrefs

This is Guy Steele's sequence GS(6, 6) (see A135416).

Cf. A000004, A142149, A086099, A142150, A142151, A001477, A062383.

Cf. A167832, A167878. - Reinhard Zumkeller, Nov 14 2009

Cf. A179526; subsequence of A007448. - Reinhard Zumkeller, Jul 18 2010

Cf. A265705.

Programs

Haskell

import Data.Bits ((.|.))
a003817 n = if n == 0 then 0 else 2 * a053644 n - 1
a003817_list = scanl (.|.) 0 [1..] :: [Integer]
-- Reinhard Zumkeller, Dec 08 2012, Jan 15 2012

Maple

A003817 := n -> n + Bits:-Nand(n, n):
seq(A003817(n), n=0..61); # Peter Luschny, Sep 23 2019

Mathematica

a[0] = 0; a[n_] := a[n] = BitOr[ a[n-1], n]; Table[a[n], {n, 0, 61}] (* Jean-François Alcover, Dec 19 2011 *)
nxt[{n_,a_}]:={n+1,BitOr[a,n+1]}; Transpose[NestList[nxt,{0,0},70]] [[2]] (* Harvey P. Dale, May 06 2016 *)
2^BitLength[Range[0,100]]-1 (* Paolo Xausa, Feb 08 2024 *)

PARI

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

Python

def a(n): return 0 if n==0 else 1 + 2*a(int(n/2)) # Indranil Ghosh, Apr 28 2017

Python

def A003817(n): return (1<Chai Wah Wu, Jul 17 2024

Formula

a(n) = a(n-1) + n*(1-floor(a(n-1)/n)). If 2^(k-1) <= n < 2^k, a(n) = 2^k - 1. - Benoit Cloitre, Aug 25 2002

a(n) = 1 + 2*a(floor(n/2)) for n > 0. - Benoit Cloitre, Apr 04 2003

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

a(n) = 2*A053644(n)-1 = A092323(n) + A053644(n). - Reinhard Zumkeller, Feb 15 2004; corrected by Anthony Browne, Jun 26 2016

a(n) = OR{k OR (n-k): 0<=k<=n}. - Reinhard Zumkeller, Jul 15 2008

For n>0: a(n+1) = A035327(n) + n = A035327(n) XOR n. - Reinhard Zumkeller, Nov 14 2009

A092323(n+1) = floor(a(n)/2). - Reinhard Zumkeller, Jul 18 2010

a(n) = A265705(n,0) = A265705(n,n). - Reinhard Zumkeller, Dec 15 2015

a(n) = A062383(n) - 1.

G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x). - Ilya Gutkovskiy, Aug 31 2019

a(n) >= A175039(n) - Austin Shapiro, Dec 29 2022