Discovered fascinating number sequence with PB

Developed or developing a new product in PureBasic? Tell the world about it.
doctornash
Enthusiast
Enthusiast
Posts: 130
Joined: Thu Oct 20, 2011 7:22 am

Discovered fascinating number sequence with PB

Post by doctornash »

I haven't come across this in https://oeis.org or other online search, so thought I'd post it here for a peer review (and share the simple but ineifficient 'big number' code I used in the calculation):
In the 'classical' Tribonacci sequence, each value is the sum of the previous three, like so:
T(n)= T(n-1) + T(n-2) + T(n-3) where n>2 with initial values: T(0) = 0, T(1) = 1, T(2) = 1
So the first few numbers in the sequence are 0,1,1,2,4,7,13,24,44,81,149...

But if instead we do this:
T(n) = T(n-1) + pT(n-2) - pT(n-3) where n>2 with initial values: T(0) = 0, T(1) = 1, T(2) = c where c and p are variables > 1
and then we take as the Output the modulus of T(n) with a variable m ie Output = T(n)%m where m>1, we get the following intriguing results upon plotting the Output for various p, c and m values:

1. A 'detailed' and a corresponding 'coarse'/'envelope resolution' waveform are obtained for c = r*(m)+2 and c = r*(m)+1 respectively, where r=1,2,3...
2. If both p and m are even, a 'detailed' and a corresponding 'coarse'/'envelope resolution' waveform are obtained for c = s*(m) and c = s*(m)+1 respectively, where s=0.5,1.5,2.5...

Examples:
Image
Image
Fo ther p=2, m=34 case, here is a zoomed in view for one period of the 'detailed' waveform at c=36 (blue), and corresponding 'coarse' waveform at c=35 (orange)
One period (period=16) of 'detailed' waveform: [4,6,10,14,22,30,12,28,26,24,20,16,8,0,18,2]
One period (period=16) of 'coarse' waveform: [3,3,7,7,15,15,31,31,29,29,25,25,17,17,1,1]
The coarse waveform is not in phase with the detailed one - the former leads the latter by one unit:
Image
If we shift the coarse waveform back by one unit so that it is aligned with the detailed one, we can see better see how they track. The 'coarse' one does not pick up the sharp changes in the 'detailed' waveform but traces its envelope or 'trend':
Image
For the sake of comparison, in yellow is an approximation of the waveform using the Haar wavelet transform -we see it does roughly 'outline' the sharp changes of the blue waveform unlike our orange one (despite the 'stepped' nature of them both) :
Image
For p=2, the following code is enough to generate the sequence to 100 numbers (as a quad is large enough to hold the generated numbers):

Code: Select all

a.q = 0
b.q = 1
c.q=28 ;vary this
d.q

m=18 ;vary this
p = 2 ;vary this

 For s = 0 To 100
   d = -p*a + p*b + c
   k = d%m
   Scaledk.d = (9/m)*k ;this simply normalizes k to between 0 and 9 so that all the waveforms can be seen on the same scale, regardless of the value of m
   Debug Scaledk
   a = b
   b = c
   c = d
 Next 
But for other values of p, the numbers become very large very quickly so I employed 'strings arithmetic' using the following procedures to add, multiply and subtract the numbers. Note that these procedures have the following limitations, as they only needed to handle the type of expression above:
SubtractNumbers: subtracts a a smaller from a larger positive number
MultiplyNumbers: multiplies a single digit positive number with a large positive number

Code: Select all

Procedure.s AddNumbers(str1.s, str2.s) 
result.s = ""
carry.l = 0
addition.l
    
str1 = ReverseString(str1)
str2 = ReverseString(str2)

    If Len(str1)=>Len(str2)
      BigStr.s = str1
    Else
      BigStr = str2
    EndIf
    
    For t = 1 To Len(BigStr)
      addition = Val(Mid(str1,t,1)) + Val(Mid(str2,t,1)) + carry
      result = result + Str(addition%10)
      carry = addition/10
    Next
    
    If carry>0
    result = result + carry
    EndIf 
    
    result = ReverseString(result)
    ProcedureReturn result
    
EndProcedure    


Procedure.l Modulus(num.s,a.l) 
  res = 0
  For t = 1 To Len(num)
    res = (res*10 + Val(Mid(num,t,1)))%a
  Next
ProcedureReturn res  
EndProcedure  

Procedure.s SubractNumbers(str1.s, str2.s) 
result.s = ""
carry.l = 0
addition.l
    
str1 = ReverseString(str1)
str2 = ReverseString(str2)

    If Len(str1)=>Len(str2)
      BigStr.s = str1
    Else
      BigStr = str2
    EndIf
    
    For t = 1 To Len(BigStr)
      subtract = Val(Mid(str1,t,1)) - (Val(Mid(str2,t,1)) + carry)
      If subtract<0
        subtract = (Val(Mid(str1,t,1))+10) - (Val(Mid(str2,t,1)) + carry)
        carry = 1
      Else
        carry = 0
      EndIf 
      result = result + Str(subtract)
    Next
    
    result = ReverseString(result)
    ProcedureReturn result
    
  EndProcedure 
  
  
Procedure.s MultiplyNumbers(str1.s, str2.s) 
result.s = ""
carry.l = 0
multiplication.l
    
    If Len(str1)=>Len(str2)
      BigStr.s = str1
      LittleStr.s = str2
    Else
      BigStr = str2
      LittleStr = str1
    EndIf
    
    BigStr = ReverseString(BigStr)
    
    For t = 1 To Len(BigStr)
      multiplication = (Val(Mid(BigStr,t,1)) * Val(LittleStr)) + carry
      If t<Len(BigStr)
        result = result + Str(multiplication%10)
        carry = multiplication/10
      Else
        result = result + ReverseString(Str(multiplication))
      EndIf  
    Next
       
    result = ReverseString(result)
    ProcedureReturn result
    
EndProcedure 

a.s = "0"
b.s = "1"
c.s = "39" ;vary this
d.s = "0"

m = 38 ;vary this
p.s = "3" ;vary this

  For f = 0 To 100
   ;The below implements with strings, the following: d = -p*a + p*b + c
   d = AddNumbers(SubractNumbers(MultiplyNumbers(p,b),MultiplyNumbers(p,a)),c)
   k = Modulus(d,m)
   Scaledk.d = (9/m)*k 
   Debug Scaledk
   a = b
   b = c
   c = d
 Next
User avatar
NicTheQuick
Addict
Addict
Posts: 1218
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Discovered fascinating number sequence with PB

Post by NicTheQuick »

You do not have to implement string arithmetic. Just use modulo correctly.

Code: Select all

a.q = 0
b.q = 1
c.q=28 ;vary this
d.q

m=18 ;vary this
p = 2;vary this

Procedure.q CorrectMod(a.q, b.q)
	a % b
	If a < 0
		ProcedureReturn a + b
	EndIf
	ProcedureReturn a
EndProcedure

For s = 0 To 1000
	d = CorrectMod(-p*a + p*b + c, m)
	Debug d
	a = b
	b = c
	c = d
Next 
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
doctornash
Enthusiast
Enthusiast
Posts: 130
Joined: Thu Oct 20, 2011 7:22 am

Re: Discovered fascinating number sequence with PB

Post by doctornash »

Here's the code for the sequence grapher, with which I came across this interesting phenomenon (substituting NicTheQuick's suggestion for the sequence generation rather than using my original cumbersome string-based routines - thanks very much for that!)
It features sliders for changing the values of c and m, but not p (as I was doing that directly in code), but that can be easily included of course.
PS How about 'coficups' as a name for this - as in: coarse-fine-couple-sequences? :mrgreen:

Code: Select all

Enumeration
  #Gadget_Canvas
EndEnumeration  

Global M.l = 9
Global C.l = 12

Global Dim MyArr.d(100)
 
Procedure.q Modulus(a.q,b.q)
  a%b
  If a<b
   ProcedureReturn a+b
  EndIf
  ProcedureReturn a
EndProcedure  


Procedure GenerateSequence()
  
aii.q = 0
bii.q = 1
cii.q = C
dii.q

 For f = 0 To 100
  dii = Modulus(-2*aii + 2*bii + cii,M) ;Experiment with this expression
  koo = dii%M
  MyArr(f) = (9/M)*koo  
   aii = bii
   bii = cii
   cii = dii
 Next 

EndProcedure

GenerateSequence()

Procedure DrawGraph()
 StartDrawing(CanvasOutput(#GADGET_Canvas))  
 Box(0,0,600,101,$FFFFFF)
 LineXY(0, 50, 600, 50, $00FF00)
 
 For t = 0 To ArraySize(MyArr())
   If t>0
    TheX = t*6
    TheY = ((-100/9)*MyArr(t))+100
    OldX = (t-1)*6
    OldY = ((-100/9)*MyArr(t-1))+100
    
    LineXY(TheX, TheY, OldX, OldY,128)
  EndIf  
Next t 
StopDrawing()

EndProcedure  


If OpenWindow(0, 0, 0, 620, 200, "Sequence Grapher", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
  CanvasGadget(#GADGET_Canvas, 10, 10, 600, 101, #PB_Canvas_ClipMouse)
      
      TrackBarGadget(502, 30, 135, 300, 20, 1, 50) ;M
      TrackBarGadget(503, 30, 155, 300, 20, 1, 50) ;C
  
      TextGadget(602, 330,135, 40, 20, "9")
      TextGadget(603, 330,155, 40, 20, "12")
      TextGadget(604, 20,135, 40, 20, "M")
      TextGadget(605, 20,155, 40, 20, "C")
      
      SetGadgetState(502, 9)
      SetGadgetState(503, 12)
      
      DrawGraph()
  
  Repeat
    Event = WaitWindowEvent()
    
    If Event = #PB_Event_Gadget
    
      Select EventGadget()
        Case 502
          SetGadgetText(602, Str(GetGadgetState(502)))
          M = GetGadgetState(502)
          GenerateSequence()
          DrawGraph()
        Case 503
          SetGadgetText(603, Str(GetGadgetState(503)))
          C = GetGadgetState(503)
          GenerateSequence()
          DrawGraph()     
          
      EndSelect
    
    EndIf
    
  Until Event = #PB_Event_CloseWindow

EndIf
doctornash
Enthusiast
Enthusiast
Posts: 130
Joined: Thu Oct 20, 2011 7:22 am

Re: Discovered fascinating number sequence with PB

Post by doctornash »

With the sequence grapher, by changing the initial values from aii.q = 0, bii.q = 1 to aii.q=0, bii.q=0 and observing the resulting sequences, we can summarize the relations as follows:

If T(n) = T(n-1) + 2T(n-2) -2T(n-3) and W(n) = T(n) mod m, a series of related sequences w(n), w'(n), w''(n) are obtained as follows:

Relation 1

This relation holds for all m:

Let w(n) be the sequence with initial values T(0)=0, T(1)=1, T(2)=m+2
Let w'(n) be the sequence with initial values T(0)=0, T(1)=0, T(2) = m+2
Let w''(n) be the sequence with initial values T(0)=0, T(1)=1 T(2) = m+1

Then if we call w(n) the 'detailed' sequence, w'(n) is a 'coarse' representation of the 'detailed' sequence, and w''(n) is a slightly coarser (and slightly horizontally shfited) representation of the 'detailed' sequence

Example:
For m=17:
w(n) is the blue sequence
w'(n) is the red sequence
w''(n) is the yellow sequence (shifted back by one unit). This one is 'slightly coarser' because it doesn't trace out the largest spike like w'(n) does
Image

Relation 2

This relation holds for even m:

Let w(n) be the sequence with initial values T(0)=0, T(1)=1, T(2)=m/2
Let w'(n) be the sequence with initial values T(0)=0, T(1)=1, T(2) = (m/2)+1

Then if we call w(n) the 'detailed' sequence, w'(n) is a 'coarse' (and slightly horizontally shifted) representation of the 'detailed' sequence

Example:
For m=22:
w(n) is the blue sequence
w'(n) is the orange sequence (shifted forward by one unit)
Image
jack
Addict
Addict
Posts: 1336
Joined: Fri Apr 25, 2003 11:10 pm

Re: Discovered fascinating number sequence with PB

Post by jack »

hello doctornash
have you presented your findings in other forums ?
perhaps http://www.mersenneforum.org/index.php , the site is mostly about primes but there are some members that are mathematicians and it might be interesting to have their input.
if you are a user of Mathematica then may I suggest http://community.wolfram.com and https://mathematica.stackexchange.com
doctornash
Enthusiast
Enthusiast
Posts: 130
Joined: Thu Oct 20, 2011 7:22 am

Re: Discovered fascinating number sequence with PB

Post by doctornash »

Thanks for the tip jack, I am indeed getting good engagement and input from members of mersenneforum re this topic:
http://www.mersenneforum.org/showthread.php?t=23501
coffee
User
User
Posts: 77
Joined: Fri Oct 06, 2017 10:43 am

Re: Discovered fascinating number sequence with PB

Post by coffee »

this looks neat. i am not math guy, but would it be possible to use it for Signal Denoising?

http://doc.opendtect.org/5.0.0/doc/od_u ... /ceemd.htm

as an example:
https://wattsupwiththat.wordpress.com/2 ... -sunspots/

the ceemd method it complex, maybe with your discovery denoising could be easy and fast.
User avatar
NicTheQuick
Addict
Addict
Posts: 1218
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Discovered fascinating number sequence with PB

Post by NicTheQuick »

:lol:
That is a totally different topic what you are talking about.
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
doctornash
Enthusiast
Enthusiast
Posts: 130
Joined: Thu Oct 20, 2011 7:22 am

Re: Discovered fascinating number sequence with PB

Post by doctornash »

Well one of the by-products of this activity has been the listing of a new sequence A316742 at https://oeis.org/.
Once again thanks for the suggestion to raise this at http://www.mersenneforum.org/index.php...one never knows where a line of investigation can lead :)
Post Reply