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
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
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<
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
A092323(n+1) = floor(a(n)/2). - Reinhard Zumkeller, Jul 18 2010
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
Comments