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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063882 a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1. 15
1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 17, 17, 17, 18, 18, 19, 20, 20, 21, 21, 22, 22, 22, 23, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 34, 34, 35, 35, 36, 37, 37, 38, 38, 39, 39, 40 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

A captivating recursive function. A meta-Fibonacci recursion.

This has been completely analyzed by Balamohan et al. They prove that the sequence a(n) is monotonic, with successive terms increasing by 0 or 1, so the sequence hits every positive integer.

They demonstrate certain special structural properties and periodicities of the associated frequency sequence (the number of times a(n) hits each positive integer) that make possible an iterative computation of a(n) for any value of n.

Further, they derive a natural partition of the a-sequence into blocks of consecutive terms ("generations") with the property that terms in one block determine the terms in the next.

a(A202014(n)) = n and a(m) < n for m < A202014(n). [Reinhard Zumkeller, Dec 08 2011]

REFERENCES

Kellie O'Connor Gutman (RKLGutman(AT)aol.com), p. 50 of "The Mathematical Intelligencer", Volume 23, Number 3, Summer 2001

LINKS

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 1..10000

B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.

Index entries for Hofstadter-type sequences

FORMULA

n/2 < a(n) <= n/2 - log_2 (n) - 1 for all n > 6 [Balamohan et al.]

MAPLE

a := proc(n) option remember; if n<=4 then 1 else if n > a(n-1) and n > a(n-4) then RETURN(a(n-a(n-1))+a(n-a(n-4))); else ERROR(" died at n= ", n); fi; fi; end;

MATHEMATICA

a[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = a[n-a[n-1]] + a[n-a[n-4]]

PROG

(Haskell)

a063882 n = a063882_list !! (n-1)

a063882_list = 1 : 1 : 1 : 1 : zipWith (+)

   (map a063882 $ zipWith (-) [5..] a063882_list)

   (map a063882 $ zipWith (-) [5..] $ drop 3 a063882_list)

-- Reinhard Zumkeller, Dec 08 2011

CROSSREFS

Cf. A132157. For partial sums see A129632.

A136036(n) = a(n+1) - a(n).

Cf. A063892, A087777.

Cf. A132174, A132175, A132176, A132177.

Cf. A202016 (occur only once).

Sequence in context: A046108 A079411 A198454 * A097873 A005375 A138370

Adjacent sequences:  A063879 A063880 A063881 * A063883 A063884 A063885

KEYWORD

nice,nonn

AUTHOR

Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001

EXTENSIONS

Edited by N. J. A. Sloane, Nov 06 2007

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified December 17 19:18 EST 2014. Contains 252038 sequences.