login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003817 a(0) = 0, a(n) = a(n-1) OR n. 20

%I

%S 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,

%T 31,31,31,31,31,31,31,63,63,63,63,63,63,63,63,63,63,63,63,63,63,63,63,

%U 63,63,63,63,63,63,63,63,63,63,63,63,63,63

%N a(0) = 0, a(n) = a(n-1) OR n.

%C Also, 0+1+2+...+n in lunar arithmetic in base 2 written in base 10. - _N. J. A. Sloane_, Oct 02 2010

%C Comment from _Michel ten Voorde_, Jun 20 2001: Consider 'triangles' with lengths n X n, constructed of unit squares. Then a(n) is the minimal number of squares (of any size) whose union is the triangle. The triangle for n=4 is:

%C .__.__.__.__

%C |1.|2.|3.|4.|

%C |__|__|__|__|

%C ...|5.|6.|7.|

%C ...|__|__|__|

%C ......|8.|9.|

%C ......|__|__|

%C .........|10|

%C .........|__|

%C The minimal number of squares to cover this is 7, namely square 3-4-6-7, square 1, square 2, square 5, square 8, square 9 and square 10.

%C For n>0: replace all 0's with 1's in binary representation of n. - _Reinhard Zumkeller_, Jul 14 2003

%C For n>0: a(n+1) = A035327(n) + n = A035327(n) XOR n. - _Reinhard Zumkeller_, Nov 14 2009

%C A092323(n+1) = floor(a(n)/2). - _Reinhard Zumkeller_, Jul 18 2010

%C a(n) = A265705(n,0) = A265705(n,n). - _Reinhard Zumkeller_, Dec 15 2015

%H R. Zumkeller, <a href="/A003817/b003817.txt">Table of n, a(n) for n = 0..10000</a> [From _Reinhard Zumkeller_, Nov 14 2009]

%H D. Applegate, M. LeBrun and N. J. A. Sloane, <a href="http://arxiv.org/abs/1107.1130">Dismal Arithmetic</a>, 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]

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

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

%H R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H R. Zumkeller, <a href="/A142149/a142149.txt">Logical Convolutions</a>

%H <a href="/index/Di#dismal">Index entries for sequences related to dismal (or lunar) arithmetic</a>

%F 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

%F a(n) = 1 + 2*a(floor(n/2)) for n > 0. - _Benoit Cloitre_, Apr 04 2003

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

%F a(n) = 2*A053644(n)-1 = A092323(n) + A053644(n). - _Reinhard Zumkeller_, Feb 15 2004; corrected by _Anthony Browne_, Jun 26 2016

%F a(n) = OR{k OR (n-k): 0<=k<=n}. - _Reinhard Zumkeller_, Jul 15 2008

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

%t 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 *)

%t nxt[{n_,a_}]:={n+1,BitOr[a,n+1]}; Transpose[NestList[nxt,{0,0},70]] [[2]] (* _Harvey P. Dale_, May 06 2016 *)

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

%o (Haskell)

%o import Data.Bits ((.|.))

%o a003817 n = if n == 0 then 0 else 2 * a053644 n - 1

%o a003817_list = scanl (.|.) 0 [1..] :: [Integer]

%o -- _Reinhard Zumkeller_, Dec 08 2012, Jan 15 2012

%o (Python)

%o def a(n): return 0 if n==0 else 1 + 2*a(int(n/2)) # _Indranil Ghosh_, Apr 28 2017

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

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

%Y Cf. A167832, A167878. - _Reinhard Zumkeller_, Nov 14 2009

%Y Cf. A179526; subsequence of A007448. - _Reinhard Zumkeller_, Jul 18 2010

%Y Cf. A265705.

%K nonn,base,nice

%O 0,3

%A _Marc LeBrun_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 15 16:25 EST 2019. Contains 320136 sequences. (Running on oeis4.)