mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2018-07-11, 10:59   #1
doctornash
 
Jul 2018

112 Posts
Thumbs up 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
doctornash is offline   Reply With Quote
Old 2018-07-11, 14:36   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

Quote:
Originally Posted by doctornash View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-07-12, 01:29   #3
doctornash
 
Jul 2018

3 Posts
Default

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
doctornash is offline   Reply With Quote
Old 2018-07-12, 01:48   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

63078 Posts
Default

Quote:
Originally Posted by doctornash View Post
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).
Dr Sardonicus is offline   Reply With Quote
Old 2018-07-12, 12:11   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
If m = p, an odd prime, the period (mod p) is twice the multiplicative order of 2 (mod p).
Magic! How does it work?
CRGreathouse is offline   Reply With Quote
Old 2018-07-12, 12:32   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by doctornash View Post
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 View Post
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.....
Covered pretty well by A027383. Add any comments/formulas/etc. you have to A027383 instead (adjusting offset as appropriate).

Quote:
Originally Posted by doctornash View Post
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.

Note the link
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-07-12, 15:26   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,271 Posts
Default

Quote:
Originally Posted by doctornash View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2018-07-14, 00:06   #8
doctornash
 
Jul 2018

3 Posts
Default

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....
doctornash is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Search for all amicable pairs up to 2^64 Sergei Chernykh Aliquot Sequences 37 2018-01-27 19:23
LL periodic residues (For Double Checks) pdazzl PrimeNet 12 2014-05-28 12:00
100M-digit n/k pairs __HRB__ Riesel Prime Search 0 2010-05-22 01:17
Rejected k/n pairs em99010pepe No Prime Left Behind 18 2008-12-06 12:50
Double-checks come in pairs? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.