 mersenneforum.org Fascinating periodic sequence pairs
 Register FAQ Search Today's Posts Mark Forums Read 2018-07-11, 10:59 #1 doctornash   Jul 2018 112 Posts Fascinating periodic sequence pairs I am developing a sound synthesizer whose waveforms are based on periodic number sequences, during the course of which I chanced across the following relations, and I'd be grateful for any help in characterizing/formalizing these observations: Let w(n) = w(n-1) + 2*w(n-2) - 2*w(n-3). Let a(n) = w(n) mod m. Observation 1 Set a(n) as the sequence with initial values w(0)=0, w(1)=1, w(2)=m+2. Set a'(n) as the sequence with initial values w(0)=0, w(1)=0, w(2)=m+2. Then if we call a(n) the 'detailed' sequence, a'(n) is the corresponding 'sample and hold'/'coarse'/'envelope following' sequence (not sure what to call it). Example, for m=17: a(n) has initial values w(0)=0, w(1)=1, w(2)=19, and the sequence is: 0,1,2,4,6,10,14,5,13,12,11,9,7,3,16,8,0,1,2,4,6,10,14,5,13,12,11,9... a'(n) has initial values w(0)=0, w(1)=0, w(2)=19, and the sequence is: 0,0,2,2,6,6,14,14,13,13,11,11,7,7,16,16,0,0,2,2,6,6,14,14,13,13,11,11... Here is a graph of these sequences a(n) and a''(n) on the same axes: https://i.imgur.com/jI0Lwta.png Observation 2 For even m: Set a(n) as the sequence with initial values w(0)=0, w(1)=1, w(2)=m/2. Set a'(n) as the sequence with initial values w(0)=0, w(1)=1, w(2)=(m/2)+1. Let a''(n) = a'(n-1)+1. Then if a(n) is the 'detailed' sequence, a''(n) is the corresponding 'envelope' sequence. Example for m=34: a(n) has initial values w(0)=0, w(1)=1, w(2)=17, and the sequence is: 0,1,17,19,17,21,17,25,17,33,17,15,17,13,17,9,17,1,17,19,17,21,17,25,17,33,17,15... a'(n) has initial values w(0)=1, w(1)=1, w(2)=18, and the sequence is: 0,1,18,20,20,24,24,32,32,14,14,12,12,8,8,0,0,18,18,20,20,24,24,32,32... Sequence a''(n) is obtained by adding 1 to every value of a'(n) and then shifting all values forward by 1 place: -,1,2,19,21,21,25,25,33,33,15,15,13,13,9,9,1,1,19,19,21,21,25,25,33,33,15,15... Here is a graph of these sequences a(n) and a''(n) on the same axes: https://i.imgur.com/Z4qKJ4u.png The discovery of above recursion formula which yields these interesting 'detailed' and 'envelope' sequences simply by incrementing a couple of the initial values, has provided a very simple way of obtaining additional sonic diversity from the synthesizer    2018-07-11, 14:36   #2
CRGreathouse

Aug 2006

2·3·977 Posts Quote:
 Originally Posted by doctornash I am developing a sound synthesizer whose waveforms are based on periodic number sequences, during the course of which I chanced across the following relations, and I'd be grateful for any help in characterizing/formalizing these observations: Let w(n) = w(n-1) + 2*w(n-2) - 2*w(n-3). Let a(n) = w(n) mod m. Observation 1 Set a(n) as the sequence with initial values w(0)=0, w(1)=1, w(2)=m+2. Set a'(n) as the sequence with initial values w(0)=0, w(1)=0, w(2)=m+2. Then if we call a(n) the 'detailed' sequence, a'(n) is the corresponding 'sample and hold'/'coarse'/'envelope following' sequence (not sure what to call it).
The first is a(n) = A027383(n-1) mod m. The second is a'(n) = (2^floor(n/2+ 1) - 2) mod m.   2018-07-12, 01:29 #3 doctornash   Jul 2018 3 Posts Thanks very much. So if we consider the sequences without the mod m and compare with what's currently in OEIS, would you agree there is justification for the following submissions? 1) A027383 is 1,2,4,8,10,14,22,30... a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3), with a(0)=0, a(1)=1, a(2)=2 is: 0,1,2,4,,8,10,14,22,30..... Action: Add a new sequence in OEIS for a(n), with a cross-reference that A027383 is a(n+1) 2) A077957 Powers of 2 alternating with zeros: 1,0,2,0,4,0,8,0,16,0,32... Action: Add a comment that this is also defined by a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3), with a(0)=1, a(1)=0, a(2)=2 3) A056453 Number of palindromes of length n using exactly two different symbols: 0,0,2,2,6,6,14,14,30,30,62,62,126,126,254,254... states as the formulae: a(n) = 2^floor((n+1)/2) - 2. a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) Action: No action, as the above entry already appears to cover a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) with a(0)=0, a(1)=0, a(2)=2. 4) (n) = a(n-1) + 2*a(n-2) - 2*a(n-3) with a(0)=1, a(1)=0, a(2)=3 produces this interesting looking sequence: 1,0,3,1,7,3,15,7,31,15,63,31,127,63,255,127,511... where every fourth number from every skipped number is the same Action: Suggest this sequence to be added to OEIS   2018-07-12, 01:48   #4
Dr Sardonicus

Feb 2017
Nowhere

63078 Posts Quote:
 Originally Posted by doctornash I am developing a sound synthesizer whose waveforms are based on periodic number sequences, during the course of which I chanced across the following relations, and I'd be grateful for any help in characterizing/formalizing these observations: Let w(n) = w(n-1) + 2*w(n-2) - 2*w(n-3). Let a(n) = w(n) mod m.
This is a linear recurrence with constant coefficients. The characteristic polynomial is

x^3 - x^2 - 2*x + 2 = (x - 1)*(x^2 - 2).

If m = p, an odd prime, the period (mod p) is twice the multiplicative order of 2 (mod p).   2018-07-12, 12:11   #5
CRGreathouse

Aug 2006

2×3×977 Posts Quote:
 Originally Posted by Dr Sardonicus If m = p, an odd prime, the period (mod p) is twice the multiplicative order of 2 (mod p).
Magic! How does it work?   2018-07-12, 12:32   #6
CRGreathouse

Aug 2006

2×3×977 Posts Quote:
 Originally Posted by doctornash would you agree there is justification for the following submissions?
Generally recurrence relations aren't all that interesting without context, but I'll look over your ideas.

Quote:
 Originally Posted by doctornash 1) A027383 is 1,2,4,8,10,14,22,30... a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3), with a(0)=0, a(1)=1, a(2)=2 is: 0,1,2,4,,8,10,14,22,30.....

Quote:
 Originally Posted by doctornash 2) A077957 Powers of 2 alternating with zeros: 1,0,2,0,4,0,8,0,16,0,32... Action: Add a comment that this is also defined by a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3), with a(0)=1, a(1)=0, a(2)=2
Unless you have something to say beyond the formula itself, this should go in the formula section. But yes, please add it.

Index entries for linear recurrences with constant coefficients, signature (0,2).
which is the same as saying "For large enough n, a(n) = 0*a(n-1) + 2*a(n-2)" or in this case "For n > 1, a(n) = 2*a(n-2)". This is the unique recurrence relation of minimal order (order = number of elements = 2 in this case); you are suggesting signature (1,2,-2) which this sequence also satisfies. You can transform that recurrence into yours:

a(n) = 2*a(n-2)
a(n-1) = 2*a(n-3)
a(n-1) - 2*a(n-3) = 0
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3)

where the last line is the sum of lines 1 and 3.

Quote:
 Originally Posted by doctornash 4) (n) = a(n-1) + 2*a(n-2) - 2*a(n-3) with a(0)=1, a(1)=0, a(2)=3 produces this interesting looking sequence: 1,0,3,1,7,3,15,7,31,15,63,31,127,63,255,127,511... where every fourth number from every skipped number is the same
That does look interesting, go for it.   2018-07-12, 15:26   #7
Dr Sardonicus

Feb 2017
Nowhere

3,271 Posts Quote:
 Originally Posted by doctornash 4) (n) = a(n-1) + 2*a(n-2) - 2*a(n-3) with a(0)=1, a(1)=0, a(2)=3 produces this interesting looking sequence: 1,0,3,1,7,3,15,7,31,15,63,31,127,63,255,127,511... where every fourth number from every skipped number is the same
It's actually an example of "Taking one step back for every two steps forward."
? forstep(i=1,9,[-1,2],print(2^i-1))
1
0
3
1
7
3
15
7
31
15
63
31
127
63
255
127
511
255   2018-07-14, 00:06 #8 doctornash   Jul 2018 3 Posts So a name for this one could be 'One step back, two steps forward Mersenne numbers'? With a cross-reference to A000225. The sequence modulo m is periodic or eventually periodic with periods being 1 (at n=2^a) or 3 or multiples of 2 (can these periods be ascertained from the (1,0,3) signature, with the '0' pertaining to the evens?): 1,1,4,1,8,4,3,1,12,8,20,4,24,3,8,1,16,12,36,8,12,20,22,4,40,24,36,3,56,8,10,1,20,16,24,12....  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Sergei Chernykh Aliquot Sequences 37 2018-01-27 19:23 pdazzl PrimeNet 12 2014-05-28 12:00 __HRB__ Riesel Prime Search 0 2010-05-22 01:17 em99010pepe No Prime Left Behind 18 2008-12-06 12:50 BigRed Software 1 2002-10-20 05:29

All times are UTC. The time now is 02:42.

Thu Jul 9 02:42:18 UTC 2020 up 106 days, 15 mins, 0 users, load averages: 2.05, 1.91, 1.81