Douglas Hofstadter's sequences
A chaotic sequence
The first of these sequences is from the book 'Gödel Escher Bach' by Douglas Hofstadter.
It is "The Hofstadter Q-sequence"
A005185
in the enciclopedy of N.J.A. Sloane.
Like the Fibonacci and Lucas sequences, each term is the sum of two preceding terms, but not the two last terms:
(The definition of Fibonacci is simpler : F(n) = F(n-1) + F(n-2)).
Example : calculation of Q(18)
Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)), the two terms Q(n-1) and Q(n-2), give two shifts starting from N allowing to find the indices n-Q(n-1) et n-Q(n-2) of the two terms to be added.
The first terms are Q(1)=1, 1, 2, 3, 3, 4, 5, Q(8)=5, Q(9)=6, 6, 6, 8, 8, 8, 10, Q(16)=9, Q(17)=10, Q(18)= ...
To calculate Q(18), it is observed that the two preceding elements are Q(17)=10 and Q(16)=9. Instead of adding these two numbers, as one would have done for Fibonacci, one shifts of 10 and 9 starting from row 18 : in 18-10=8 and 18-9=9, the two values to be added are Q(8)=5 and Q(9)=6, from where Q(18)=5+6=11.
The sequence has a moderately erratic behavior, perhaps chaotic, but it is not certain, the graphs let think of a certain form of regularity.
Sequence Q(n) for n in the range [a ; b]
Page with the java applet
Like the Fibonacci and Lucas sequences, each term is the sum of two preceding terms, but not the two last terms:
| Q(1) = Q(2) = 1 et pour n > 2, Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2)) |
(The definition of Fibonacci is simpler : F(n) = F(n-1) + F(n-2)).
| Hofstadter's Q-sequence |
|
| Terms of indices 1 to 200 000 (or 3 500) of the Q-sequence |
Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)), the two terms Q(n-1) and Q(n-2), give two shifts starting from N allowing to find the indices n-Q(n-1) et n-Q(n-2) of the two terms to be added.
The first terms are Q(1)=1, 1, 2, 3, 3, 4, 5, Q(8)=5, Q(9)=6, 6, 6, 8, 8, 8, 10, Q(16)=9, Q(17)=10, Q(18)= ...
To calculate Q(18), it is observed that the two preceding elements are Q(17)=10 and Q(16)=9. Instead of adding these two numbers, as one would have done for Fibonacci, one shifts of 10 and 9 starting from row 18 : in 18-10=8 and 18-9=9, the two values to be added are Q(8)=5 and Q(9)=6, from where Q(18)=5+6=11.
The sequence has a moderately erratic behavior, perhaps chaotic, but it is not certain, the graphs let think of a certain form of regularity.
Sequence Q(n) for n in the range [a ; b]
Page with the java applet
A family of sequences of the same type
These sequences can have similar behaviors or not.
Select that whose you want to calculate terms.
Select that whose you want to calculate terms.
References, resources, links
Hofstadter-type sequences On-Line Encyclopedia of Integer Sequences
Hofstadter's Q-Sequence Eric Weisstein's world of Mathematics
Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
© (Copyright) Jean-Paul Davalan 2002-2014Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.