Padovan sequence: Difference between revisions
Added FreeBASIC
(Added FreeBASIC) |
|||
| (11 intermediate revisions by 4 users not shown) | |||
Line 638:
The floor- and L-system-based functions match from P_0 to P_31.</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">using System;
using System.Collections.Generic;
using System.Linq;
public static class Padovan
{
private static readonly List<int> recurrences = new List<int>();
private static readonly List<int> floors = new List<int>();
private const double PP = 1.324717957244746025960908854;
private const double SS = 1.0453567932525329623;
public static void Main(string[] args)
{
for (int i = 0; i < 64; i++)
{
recurrences.Add(PadovanRecurrence(i));
floors.Add(PadovanFloor(i));
}
Console.WriteLine("The first 20 terms of the Padovan sequence:");
recurrences.GetRange(0, 20).ForEach(term => Console.Write(term + " "));
Console.WriteLine(Environment.NewLine);
Console.WriteLine("Recurrence and floor functions agree for first 64 terms? " + recurrences.SequenceEqual(floors));
Console.WriteLine(Environment.NewLine);
List<string> words = CreateLSystem();
Console.WriteLine("The first 10 terms of the L-system:");
words.GetRange(0, 10).ForEach(term => Console.Write(term + " "));
Console.WriteLine(Environment.NewLine);
Console.Write("Length of first 32 terms produced from the L-system match Padovan sequence? ");
List<int> wordLengths = words.Select(s => s.Length).ToList();
Console.WriteLine(wordLengths.SequenceEqual(recurrences.GetRange(0, 32)));
}
private static int PadovanRecurrence(int n)
{
if (n <= 2)
return 1;
return recurrences[n - 2] + recurrences[n - 3];
}
private static int PadovanFloor(int n)
{
return (int)Math.Floor(Math.Pow(PP, n - 1) / SS + 0.5);
}
private static List<string> CreateLSystem()
{
List<string> words = new List<string>();
string text = "A";
while (words.Count < 32)
{
words.Add(text);
char[] textChars = text.ToCharArray();
text = "";
foreach (char ch in textChars)
{
text += ch switch
{
'A' => "B",
'B' => "C",
'C' => "AB",
_ => throw new InvalidOperationException("Unexpected character found: " + ch),
};
}
}
return words;
}
}</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
Recurrence and floor functions agree for first 64 terms? True
The first 10 terms of the L-system:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Length of first 32 terms produced from the L-system match Padovan sequence? True
</pre>
=={{header|C++}}==
Line 906 ⟶ 1,002:
readln;
end.</syntaxhighlight>
=={{header|EasyLang}}==
{{trans|Swift}}
<syntaxhighlight>
p[] = [ 1 1 1 ]
padorn = 1
func padorec .
if padorn <= 3
h = p[padorn]
else
h = p[1] + p[2]
.
p[1] = p[2]
p[2] = p[3]
p[3] = h
padorn += 1
return h
.
pfn = 1
P = 1.32471795724474602596
S = 1.0453567932525329623
#
func padofloor .
p = floor ((pow P (pfn - 2)) / S + 0.5)
pfn += 1
return p
.
str$ = "A"
func$ padolsys .
r$ = str$
for c$ in strchars str$
if c$ = "A"
nxt$ &= "B"
elif c$ = "B"
nxt$ &= "C"
else
nxt$ &= "AB"
.
.
str$ = nxt$
return r$
.
#
print "First 20 terms of the Padovan sequence:"
for i to 64
par[] &= padorec
.
for i to 20
write par[i] & " "
.
print ""
for i to 64
paf[] &= padofloor
.
if par[] = paf[]
print "\nRecurrence and floor functions agree for first 64 terms"
.
for i to 32
pal$[] &= padolsys
.
print "\nFirst 10 strings produced from the L-system:"
for i to 10
write pal$[i] & " "
.
print ""
for i to 32
if len pal$[i] <> par[i]
break 1
.
.
if i > 32
print "\nLength of first 32 strings produced from the L-system = Padovan sequence"
.
</syntaxhighlight>
{{out}}
<pre>
First 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
Recurrence and floor functions agree for first 64 terms
First 10 strings produced from the L-system:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Length of first 32 strings produced from the L-system = Padovan sequence
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<syntaxhighlight lang="Elixir"># Padovan sequence as a Stream
defmodule Padovan do
def stream do
Stream.resource(
fn -> {1, 1, 1} end,
fn {a, b, c} ->
next_value = a + b
{[a], {b, c, next_value}}
end,
fn _ -> :ok end
)
end
end
# Padovan floor function
defmodule PadovanFloorFunction do
@p 1.324717957244746025960908854
@s 1.0453567932525329623
def padovan_f(n), do: trunc((:math.pow(@p, n - 1) / @s) + 0.5)
end
# Calculate and print the first 20 elements of the Padovan sequence and the floor function
padovan_sequence = Padovan.stream() |> Enum.take(20)
padovan_floor_function = Enum.map(0..19, &PadovanFloorFunction.padovan_f(&1))
IO.puts("Recurrence Padovan: #{inspect(padovan_sequence)}")
IO.puts("Floor function: #{inspect(padovan_floor_function)}")
# Check if the sequences are equal up to n
n = 63
bool = Enum.map(0..(n-1), &PadovanFloorFunction.padovan_f(&1)) == Padovan.stream() |> Enum.take(n)
IO.puts("Recurrence and floor function are equal up to #{n}: #{bool}.")
# L-system generator as a Stream
defmodule LSystem do
def stream(axiom \\ "A", rules \\ %{"A" => "B", "B" => "C", "C" => "AB"}) do
Stream.iterate(axiom, fn string ->
string
|> String.graphemes()
|> Enum.map(&Map.get(rules, &1, ""))
|> Enum.join()
end)
end
end
# Calculate and print the first 10 elements of the L-system
l_system_sequence = LSystem.stream() |> Enum.take(10)
IO.puts("First 10 elements of L-system: #{l_system_sequence |> Enum.join(", ")}")
# Check if the sizes of the L-system strings match the Padovan sequence
n = 32
l_system_sizes = LSystem.stream() |> Enum.take(n) |> Enum.map(&String.length/1)
bool = l_system_sizes == Padovan.stream() |> Enum.take(n)
IO.puts("Sizes of first #{n} L_system strings equal to recurrence Padovan? #{bool}.")</syntaxhighlight>
{{out}}
<pre>
Recurrence Padovan: [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151]
Floor function: [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151]
Recurrence and floor function are equal up to 63: true.
First 10 elements of L-system: A, B, C, AB, BC, CAB, ABBC, BCCAB, CABABBC, ABBCBCCAB
Sizes of first 32 L_system strings equal to recurrence Padovan? true.
</pre>
=={{header|Factor}}==
Line 964 ⟶ 1,214:
The L-system, recurrence and floor based algorithms match to n=31.
</pre>
=={{header|FreeBASIC}}==
{{trans|11l}}
<syntaxhighlight lang="vbnet">Const As Double pp = 1.324717957244746025960908854
Const As Double ss = 1.0453567932525329623
Function padovan1(Byval n As Integer) As Integer
Dim As Integer a, b, c, d, i
a = 1: b = 1: c = 1
d = 1
For i = 1 To (n - 3)
d = a + b
a = b : b = c : c = d
Next i
Return d
End Function
Function padovan2(Byval n As Integer) As Integer
Dim As Double p = 1.0
For i As Integer = 1 To (n - 1)
p *= pp
Next i
Return Fix(p / ss)
End Function
Function padovan3(Byval n As Integer) As String
Dim As String sgte, s = "A"
Dim As Integer i, j, c
Dim As String rules(1 To 3) = {"B", "C", "AB"}
For i = 1 To n
sgte = ""
For j = 1 To Len(s)
Select Case Mid(s, j, 1)
Case "A" : c = 1
Case "B" : c = 2
Case "C" : c = 3
End Select
sgte &= rules(c)
Next j
s = sgte
Next i
Return s
End Function
Dim As Integer n
Print "First 20 terms of the Padovan sequence:"
For n = 1 To 20
Print padovan1(n); '" ";
Next
n = 1
Dim As Boolean areEqual = True
Dim As Integer list1(64), list2(64)
Do While n <= 64 And areEqual = False
list1(n) = padovan1(n)
list2(n) = padovan2(n)
If list1(n) <> list2(n) Then areEqual = False
n += 1
Loop
Print !"\nThe first 64 iterative and calculated values ";
Print Iif(areEqual, "are the same.", "differ.")
Print !"\nFirst 10 L-system strings:"
For n = 0 To 9
Print padovan3(n); " ";
Next
Print
areEqual = True
Dim As Integer list3(31)
Print !"\nLengths of the 32 first L-system strings:"
For n = 0 To 31
list3(n) = Len(padovan3(n))
Print list3(n); '" ";
If list3(n) <> list1(n) Then areEqual = False
Next
Print !"\nThese lengths are";
Print Iif(areEqual, " the 32 first terms of the Padovan sequence.", " not the 32 first terms of the Padovan sequence.")
Sleep</syntaxhighlight>
{{out}}
<pre>First 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
The first 64 iterative and calculated values are the same.
First 10 L-system strings:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Lengths of the 32 first L-system strings:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200 265 351 465 616 816 1081 1432 1897 2513 3329 4410
These lengths are not the 32 first terms of the Padovan sequence.</pre>
=={{header|Go}}==
Line 1,266 ⟶ 1,610:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
Line 1,732 ⟶ 2,075:
64 35676949 35676949
</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="Kotlin">import kotlin.math.floor
import kotlin.math.pow
object CodeKt{
private val recurrences = mutableListOf<Int>()
private val floors = mutableListOf<Int>()
private const val PP = 1.324717957244746025960908854
private const val SS = 1.0453567932525329623
@JvmStatic
fun main(args: Array<String>) {
for (i in 0 until 64) {
recurrences.add(padovanRecurrence(i))
floors.add(padovanFloor(i))
}
println("The first 20 terms of the Padovan sequence:")
recurrences.subList(0, 20).forEach { term -> print("$term ") }
println("\n")
println("Recurrence and floor functions agree for first 64 terms? ${recurrences == floors}\n")
val words = createLSystem()
println("The first 10 terms of the L-system:")
words.subList(0, 10).forEach { term -> print("$term ") }
println("\n")
print("Length of first 32 terms produced from the L-system match Padovan sequence? ")
val wordLengths = words.map { it.length }
println(wordLengths == recurrences.subList(0, 32))
}
private fun padovanRecurrence(n: Int): Int =
if (n <= 2) 1 else recurrences[n - 2] + recurrences[n - 3]
private fun padovanFloor(n: Int): Int =
floor(PP.pow(n - 1) / SS + 0.5).toInt()
private fun createLSystem(): List<String> {
val words = mutableListOf<String>()
var text = "A"
while (words.size < 32) {
words.add(text)
text = text.map { ch ->
when (ch) {
'A' -> "B"
'B' -> "C"
'C' -> "AB"
else -> throw AssertionError("Unexpected character found: $ch")
}
}.joinToString("")
}
return words
}
}</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
Recurrence and floor functions agree for first 64 terms? true
The first 10 terms of the L-system:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Length of first 32 terms produced from the L-system match Padovan sequence? true
</pre>
=={{header|Lua}}==
{{trans|Perl}}
<syntaxhighlight lang="Lua">-- Define the constants
local p = 1.32471795724474602596
local s = 1.0453567932525329623
-- Generator for the Padovan sequence using coroutines
function pad_recur_gen(n)
local co = coroutine.create(function ()
local p = {1, 1, 1, 2}
for i = 1, n do
local next_val = p[2] + p[3]
coroutine.yield(p[1])
table.remove(p, 1)
table.insert(p, next_val)
end
end)
return function () -- iterator
local status, value = coroutine.resume(co)
return value
end
end
-- Padovan floor function
function pad_floor(index)
if index < 3 then
return math.floor(1/2 + p)
else
return math.floor(1/2 + p^(index - 2) / s)
end
end
local l, m, n = 10, 20, 32
local pr = {}
local pad_recur = pad_recur_gen(n)
for i = 1, n do
pr[i] = pad_recur()
end
for i = 1, m do
io.write(pr[i] .. ' ')
end
io.write('\n')
local pf = {}
for i = 1, n do
pf[i] = pad_floor(i)
end
for i = 1, m do
io.write(pf[i] .. ' ')
end
io.write('\n')
local L = {'A'}
local rules = { A = 'B', B = 'C', C = 'AB' }
for i = 1, n do
local next_str = ''
for char in L[#L]:gmatch('.') do
next_str = next_str .. rules[char]
end
table.insert(L, next_str)
end
for i = 1, l do
io.write(L[i] .. ' ')
end
io.write('\n')
for i = 1, n do
assert(pr[i] == pf[i] and pr[i] == #L[i],
"Uh oh, n=" .. i .. ": " .. pr[i] .. " vs " .. pf[i] .. " vs " .. #L[i])
end
print('100% agreement among all 3 methods.')</syntaxhighlight>
{{out}}
<pre>
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
100% agreement among all 3 methods.
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Line 1,760 ⟶ 2,266:
BCCABCABABBC
True</pre>
=={{header|MATLAB}}==
<syntaxhighlight lang="MATLAB">clear all;close all;clc;
% Calculate the sequences
padovan_sequence_20 = Padovan1(20)
padovan_approx_20 = Padovan2(20)
% Check if the sequences are equal for n = 64
are_sequences_equal = isequal(Padovan1(64), Padovan2(64))
% Generate the substitution system sequence
sequence_32 = createLSystem();
words = sequence_32(1:10)
% Check if the length of the substitution system sequence equals the Padovan sequence
are_lengths_equal = all( cellfun(@(ele) length(ele), sequence_32) ...
== Padovan2(32) )
function words = createLSystem()
words = {'A'}; % Initialize cell array with one element "A"
text = 'A'; % Current text is "A"
while length(words) < 32
newText = ''; % Initialize new text as empty
for i = 1:length(text)
switch text(i)
case 'A'
newText = [newText 'B']; % Append 'B' to new text
case 'B'
newText = [newText 'C']; % Append 'C' to new text
case 'C'
newText = [newText 'AB']; % Append 'AB' to new text
end
end
text = newText; % Update text with the new text
words{end+1} = text; % Append new text to words list
end
end
function padovan_sequence = Padovan1(nmax)
padovan_sequence = zeros(1, nmax);
padovan_sequence(1:3) = [1, 1, 1];
for n = 4:nmax
padovan_sequence(n) = padovan_sequence(n-2) + padovan_sequence(n-3);
end
end
function padovan_approx = Padovan2(nmax)
p = 1.324717957244746025960908854;
s = 1.0453567932525329623;
padovan_approx = floor(p.^(-1:nmax-2) / s + 0.5);
end</syntaxhighlight>
{{out}}
<pre>
padovan_sequence_20 =
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
padovan_approx_20 =
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
are_sequences_equal =
logical
1
words =
1×10 cell array
{'A'} {'B'} {'C'} {'AB'} {'BC'} {'CAB'} {'ABBC'} {'BCCAB'} {'CABABBC'} {'ABBCBCCAB'}
are_lengths_equal =
logical
1
</pre>
=={{header|Nim}}==
Line 2,225 ⟶ 2,819:
The first 32 recurrence terms and L System lengths are the same.</pre>
=={{header|R}}==
<syntaxhighlight lang="R" line># Function to calculate Padovan sequence iteratively
padovan_sequence <- function(n) {
recurrences <- numeric(n)
recurrences[1:3] <- c(1, 1, 1)
if (n > 3) {
for (i in 4:n) {
recurrences[i] <- recurrences[i-2] + recurrences[i-3]
}
}
recurrences
}
# Function to calculate Padovan floor
padovan_floor <- function(aN) {
PP <- 1.324717957244746025960908854
SS <- 1.0453567932525329623
floor((PP^(aN - 1)) / SS + 0.5)
}
# Function to create L-system
create_l_system<- function() {
words <- c("A")
text <- "A"
while (length(words) < 32) {
text <- strsplit(text, "")[[1]] # Split the string into a list of characters
text <- sapply(text, function(char) {
if (char == "A") {
return("B")
} else if (char == "B") {
return("C")
} else if (char == "C") {
return("AB")
}
})
text <- paste(text, collapse = "") # Collapse the list back into a single string
words <- c(words, text) # Append the new word to the list
}
words
}
# Main script
num_terms <- 64
padovan_seq <- padovan_sequence(num_terms)
floors <- sapply(0:(num_terms-1), padovan_floor)
cat("The first 20 terms of the Padovan sequence:\n")
cat(padovan_seq[1:20], sep=" ", end="\n")
cat("\n")
cat("Recurrence and floor functions agree for first 64 terms?", all(padovan_seq == floors), "\n\n")
words <- create_l_system()
cat("The first 10 terms of the L-system:\n")
cat(words[1:10], sep=" ", end="\n")
cat("\n")
cat("Length of first 32 terms produced from the L-system match Padovan sequence? ")
word_lengths <- sapply(words, nchar)
cat(all(word_lengths[1:32] == padovan_seq[1:32]))</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
Recurrence and floor functions agree for first 64 terms? TRUE
The first 10 terms of the L-system:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Length of first 32 terms produced from the L-system match Padovan sequence? TRUE
</pre>
Line 2,475 ⟶ 3,148:
Length of first 32 strings produced from the L-system = Padovan sequence? true
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="scala">object Padovan extends App {
val recurrences = new collection.mutable.ListBuffer[Int]()
val floors = new collection.mutable.ListBuffer[Int]()
val PP = 1.324717957244746025960908854
val SS = 1.0453567932525329623
for (i <- 0 until 64) {
recurrences += padovanRecurrence(i)
floors += padovanFloor(i)
}
println("The first 20 terms of the Padovan sequence:")
recurrences.slice(0, 20).foreach(term => print(s"${term} "))
println("\n")
println(s"Recurrence and floor functions agree for first 64 terms? ${recurrences == floors}")
println("")
val words = createLSystem()
println("The first 10 terms of the L-system:")
words.slice(0, 10).foreach(term => print(term + " "))
println("\n")
print("Length of first 32 terms produced from the L-system match Padovan sequence? ")
val wordLengths = words.map(_.length)
print(wordLengths.slice(0, 32) == recurrences.slice(0, 32))
def padovanRecurrence(n: Int): Int = {
if (n <= 2) 1 else recurrences(n - 2) + recurrences(n - 3)
}
def padovanFloor(aN: Int): Int = {
scala.math.floor(scala.math.pow(PP, aN - 1) / SS + 0.5).toInt
}
def createLSystem(): List[String] = {
var words = List("A")
var text = "A"
while (words.length < 32) {
text = text.flatMap {
case 'A' => "B"
case 'B' => "C"
case 'C' => "AB"
}
words = words :+ text
}
words
}
}</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
Recurrence and floor functions agree for first 64 terms? true
The first 10 terms of the L-system:
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
Length of first 32 terms produced from the L-system match Padovan sequence? true
</pre>
=={{header|Swift}}==
Line 2,555 ⟶ 3,300:
Length of first 32 strings produced from the L-system = Padovan sequence? true
</pre>
=={{header|Tcl}}==
{{trans|Perl}}
<syntaxhighlight lang="Tcl">package require Tcl 8.6
# Create a coroutine for generating Padovan sequence using lazy evaluation
proc pad_recur {{n 1}} {
set p1 1
set p2 1
set p3 1
set p4 1
for {set i 1} {$i <= $n} {incr i} {
set next [expr {$p2 + $p3}]
yield $p1
set p1 $p2
set p2 $p3
set p3 $p4
set p4 $next
}
}
proc pad_floor {n} {
set p 1.32471795724474602596
set s 1.0453567932525329623
if {$n < 3} {
return 1 ;# The first three elements should be 1, so return 1 for n < 3
} else {
return [expr {int(0.5 + pow($p, double($n)-2) / $s)}]
}
}
# Main variables
set l 10
set m 20
set n 32
# Generating Padovan sequence using recursive coroutine
set pr [list]
set pad_recur_coro [coroutine pad_recur_co pad_recur $n]
for {set i 1} {$i <= $n} {incr i} {
lappend pr [pad_recur_co]
}
puts [join [lrange $pr 0 [expr {$m - 1}]] " "]
# Generating Padovan sequence using floor function
set pf [list]
for {set i 1} {$i <= $n} {incr i} {
lappend pf [pad_floor $i]
}
puts [join [lrange $pf 0 [expr {$m - 1}]] " "]
# Generating L-system sequence
set L [list "A"]
set rules [dict create A B B C C AB]
for {set i 1} {$i <= $n} {incr i} {
set last [lindex $L end]
set expansion ""
foreach char [split $last ""] {
append expansion [dict get $rules $char]
}
lappend L $expansion
}
puts [join [lrange $L 0 [expr {$l - 1}]] " "]
# Comparison of all three methods, adjusting for zero-indexing
for {set i 0} {$i < $m} {incr i} {
set pr_val [lindex $pr $i]
set pf_val [lindex $pf $i]
set L_len [string length [lindex $L $i]]
if { $pr_val != $pf_val || $pr_val != $L_len } {
error "Uh oh, n=$i: $pr_val vs $pf_val vs $L_len"
}
}
puts "100% agreement among all 3 methods."</syntaxhighlight>
{{out}}
<pre>
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151
A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB
100% agreement among all 3 methods.
</pre>
=={{header|Wren}}==
Line 2,560 ⟶ 3,394:
{{libheader|Wren-dynamic}}
L-System stuff is based on the Julia implementation.
<syntaxhighlight lang="
import "./dynamic" for Struct
var padovanRecur = Fn.new { |n|
| |||