New Order #5: where Fibonacci and Beatty meet at Wythoff Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) The PPCG Site design is on its way - help us make it awesome! Sandbox for Proposed ChallengesNew order #4: WorldNew Order #2: Turn My WayNew Order #1: How does this feel?New Order #3: 5 8 6Fibonacci function or sequencePrint the intersection of sequencesFind the Fibonacci KernelFind the closest Fibonacci NumberUpper or Lower Wythoff?What are the repeating Fibonacci Digits?New Order #1: How does this feel?New Order #2: Turn My WayNew Order #3: 5 8 6New order #4: World
Putting class ranking in CV, but against dept guidelines
What would you call this weird metallic apparatus that allows you to lift people?
Selecting user stories during sprint planning
Is it possible for SQL statements to execute concurrently within a single session in SQL Server?
How could we fake a moon landing now?
Do I really need to have a message in a novel to appeal to readers?
Why limits give us the exact value of the slope of the tangent line?
Trademark violation for app?
Effects on objects due to a brief relocation of massive amounts of mass
Find 108 by using 3,4,6
Time to Settle Down!
How do I find out the mythology and history of my Fortress?
How much damage would a cupful of neutron star matter do to the Earth?
Can a new player join a group only when a new campaign starts?
Maximum summed subsequences with non-adjacent items
What does it mean that physics no longer uses mechanical models to describe phenomena?
Sum letters are not two different
Is there a kind of relay that only consumes power when switching?
Why is it faster to reheat something than it is to cook it?
What is the meaning of 'breadth' in breadth first search?
Did Mueller's report provide an evidentiary basis for the claim of Russian govt election interference via social media?
Most bit efficient text communication method?
Monolithic + MicroServices
Did any compiler fully use 80-bit floating point?
New Order #5: where Fibonacci and Beatty meet at Wythoff
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)
The PPCG Site design is on its way - help us make it awesome!
Sandbox for Proposed ChallengesNew order #4: WorldNew Order #2: Turn My WayNew Order #1: How does this feel?New Order #3: 5 8 6Fibonacci function or sequencePrint the intersection of sequencesFind the Fibonacci KernelFind the closest Fibonacci NumberUpper or Lower Wythoff?What are the repeating Fibonacci Digits?New Order #1: How does this feel?New Order #2: Turn My WayNew Order #3: 5 8 6New order #4: World
$begingroup$
Introduction (may be ignored)
Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fifth challenge in this series (links to the first, second, third and fourth challenge).
In this challenge, we will meet the Wythoff array, which is a intertwined avalanche of Fibonacci sequences and Beatty sequences!
The Fibonacci numbers are probably for most of you a well known sequence. Given two starting numbers $F_0$ and $F_1$, the following $F_n$ are given by: $F_n = F_(n-1) + F_(n-2)$ for $n>2$.
The Beatty sequence, given a parameter $r$ is: $B^r_n = lfloor rn rfloor$ for $n ge 1$. One of the properties of the Beatty sequence is that for every parameter $r$, there is exactly one parameter $s=r/(r-1)$, such that the Beatty sequences for those parameters are disjunct and joined together, they span all natural numbers excluding 0 (e.g.: $B^r cup B^r/(r-1) = BbbN setminus 0$).
Now here comes the mindblowing part: you can create an array, where each row is a Fibonacci sequence and each column is a Beatty sequence. This array is the Wythoff array. The best part is: every positive number appears exactly once in this array! The array looks like this:
1 2 3 5 8 13 21 34 55 89 144 ...
4 7 11 18 29 47 76 123 199 322 521 ...
6 10 16 26 42 68 110 178 288 466 754 ...
9 15 24 39 63 102 165 267 432 699 1131 ...
12 20 32 52 84 136 220 356 576 932 1508 ...
14 23 37 60 97 157 254 411 665 1076 1741 ...
17 28 45 73 118 191 309 500 809 1309 2118 ...
19 31 50 81 131 212 343 555 898 1453 2351 ...
22 36 58 94 152 246 398 644 1042 1686 2728 ...
25 41 66 107 173 280 453 733 1186 1919 3105 ...
27 44 71 115 186 301 487 788 1275 2063 3338 ...
...
An element at row $m$ and column $n$ is defined as:
$A_m,n = begincases
leftlfloor lfloor mvarphi rfloor varphi rightrfloor & text if n=1\
leftlfloor lfloor mvarphi rfloor varphi^2 rightrfloor & text if n=2\
A_m,n-2+A_m,n-1 & text if n > 2
endcases$
where $varphi$ is the golden ratio: $varphi=frac1+sqrt52$.
If we follow the anti-diagonals of this array, we get A035513, which is the target sequence for this challenge (note that this sequence is added to the OEIS by Neil Sloane himself!). Since this is a "pure sequence" challenge, the task is to output $a(n)$ for a given $n$ as input, where $a(n)$ is A035513.
There are different strategies you can follow to get to $a(n)$, which makes this challenge (in my opinion) really interesting.
Task
Given an integer input $n$, output $a(n)$ in integer format, where $a(n)$ is A035513.
Note: 1-based indexing is assumed here; you may use 0-based indexing, so $a(0) = 1; a(1) = 2$, etc. Please mention this in your answer if you choose to use this.
Test cases
Input | Output
---------------
1 | 1
5 | 7
20 | 20
50 | 136
78 | 30
123 | 3194
1234 | 8212236486
3000 | 814
9999 | 108240
29890 | 637
It might be fun to know that the largest $a(n)$ for $1le nle32767$ is $a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) lfloor 2 varphirfloor + F(255).$
Rules
- Input and output are integers
- Your program should at least support input in the range of 1 up to 32767). Note that $a(n)$ goes up to 30 digit numbers in this range...
- Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
- Default I/O rules apply.
Default loopholes are forbidden.- This is code-golf, so the shortest answers in bytes wins
code-golf sequence
$endgroup$
|
show 7 more comments
$begingroup$
Introduction (may be ignored)
Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fifth challenge in this series (links to the first, second, third and fourth challenge).
In this challenge, we will meet the Wythoff array, which is a intertwined avalanche of Fibonacci sequences and Beatty sequences!
The Fibonacci numbers are probably for most of you a well known sequence. Given two starting numbers $F_0$ and $F_1$, the following $F_n$ are given by: $F_n = F_(n-1) + F_(n-2)$ for $n>2$.
The Beatty sequence, given a parameter $r$ is: $B^r_n = lfloor rn rfloor$ for $n ge 1$. One of the properties of the Beatty sequence is that for every parameter $r$, there is exactly one parameter $s=r/(r-1)$, such that the Beatty sequences for those parameters are disjunct and joined together, they span all natural numbers excluding 0 (e.g.: $B^r cup B^r/(r-1) = BbbN setminus 0$).
Now here comes the mindblowing part: you can create an array, where each row is a Fibonacci sequence and each column is a Beatty sequence. This array is the Wythoff array. The best part is: every positive number appears exactly once in this array! The array looks like this:
1 2 3 5 8 13 21 34 55 89 144 ...
4 7 11 18 29 47 76 123 199 322 521 ...
6 10 16 26 42 68 110 178 288 466 754 ...
9 15 24 39 63 102 165 267 432 699 1131 ...
12 20 32 52 84 136 220 356 576 932 1508 ...
14 23 37 60 97 157 254 411 665 1076 1741 ...
17 28 45 73 118 191 309 500 809 1309 2118 ...
19 31 50 81 131 212 343 555 898 1453 2351 ...
22 36 58 94 152 246 398 644 1042 1686 2728 ...
25 41 66 107 173 280 453 733 1186 1919 3105 ...
27 44 71 115 186 301 487 788 1275 2063 3338 ...
...
An element at row $m$ and column $n$ is defined as:
$A_m,n = begincases
leftlfloor lfloor mvarphi rfloor varphi rightrfloor & text if n=1\
leftlfloor lfloor mvarphi rfloor varphi^2 rightrfloor & text if n=2\
A_m,n-2+A_m,n-1 & text if n > 2
endcases$
where $varphi$ is the golden ratio: $varphi=frac1+sqrt52$.
If we follow the anti-diagonals of this array, we get A035513, which is the target sequence for this challenge (note that this sequence is added to the OEIS by Neil Sloane himself!). Since this is a "pure sequence" challenge, the task is to output $a(n)$ for a given $n$ as input, where $a(n)$ is A035513.
There are different strategies you can follow to get to $a(n)$, which makes this challenge (in my opinion) really interesting.
Task
Given an integer input $n$, output $a(n)$ in integer format, where $a(n)$ is A035513.
Note: 1-based indexing is assumed here; you may use 0-based indexing, so $a(0) = 1; a(1) = 2$, etc. Please mention this in your answer if you choose to use this.
Test cases
Input | Output
---------------
1 | 1
5 | 7
20 | 20
50 | 136
78 | 30
123 | 3194
1234 | 8212236486
3000 | 814
9999 | 108240
29890 | 637
It might be fun to know that the largest $a(n)$ for $1le nle32767$ is $a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) lfloor 2 varphirfloor + F(255).$
Rules
- Input and output are integers
- Your program should at least support input in the range of 1 up to 32767). Note that $a(n)$ goes up to 30 digit numbers in this range...
- Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
- Default I/O rules apply.
Default loopholes are forbidden.- This is code-golf, so the shortest answers in bytes wins
code-golf sequence
$endgroup$
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
1
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58
|
show 7 more comments
$begingroup$
Introduction (may be ignored)
Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fifth challenge in this series (links to the first, second, third and fourth challenge).
In this challenge, we will meet the Wythoff array, which is a intertwined avalanche of Fibonacci sequences and Beatty sequences!
The Fibonacci numbers are probably for most of you a well known sequence. Given two starting numbers $F_0$ and $F_1$, the following $F_n$ are given by: $F_n = F_(n-1) + F_(n-2)$ for $n>2$.
The Beatty sequence, given a parameter $r$ is: $B^r_n = lfloor rn rfloor$ for $n ge 1$. One of the properties of the Beatty sequence is that for every parameter $r$, there is exactly one parameter $s=r/(r-1)$, such that the Beatty sequences for those parameters are disjunct and joined together, they span all natural numbers excluding 0 (e.g.: $B^r cup B^r/(r-1) = BbbN setminus 0$).
Now here comes the mindblowing part: you can create an array, where each row is a Fibonacci sequence and each column is a Beatty sequence. This array is the Wythoff array. The best part is: every positive number appears exactly once in this array! The array looks like this:
1 2 3 5 8 13 21 34 55 89 144 ...
4 7 11 18 29 47 76 123 199 322 521 ...
6 10 16 26 42 68 110 178 288 466 754 ...
9 15 24 39 63 102 165 267 432 699 1131 ...
12 20 32 52 84 136 220 356 576 932 1508 ...
14 23 37 60 97 157 254 411 665 1076 1741 ...
17 28 45 73 118 191 309 500 809 1309 2118 ...
19 31 50 81 131 212 343 555 898 1453 2351 ...
22 36 58 94 152 246 398 644 1042 1686 2728 ...
25 41 66 107 173 280 453 733 1186 1919 3105 ...
27 44 71 115 186 301 487 788 1275 2063 3338 ...
...
An element at row $m$ and column $n$ is defined as:
$A_m,n = begincases
leftlfloor lfloor mvarphi rfloor varphi rightrfloor & text if n=1\
leftlfloor lfloor mvarphi rfloor varphi^2 rightrfloor & text if n=2\
A_m,n-2+A_m,n-1 & text if n > 2
endcases$
where $varphi$ is the golden ratio: $varphi=frac1+sqrt52$.
If we follow the anti-diagonals of this array, we get A035513, which is the target sequence for this challenge (note that this sequence is added to the OEIS by Neil Sloane himself!). Since this is a "pure sequence" challenge, the task is to output $a(n)$ for a given $n$ as input, where $a(n)$ is A035513.
There are different strategies you can follow to get to $a(n)$, which makes this challenge (in my opinion) really interesting.
Task
Given an integer input $n$, output $a(n)$ in integer format, where $a(n)$ is A035513.
Note: 1-based indexing is assumed here; you may use 0-based indexing, so $a(0) = 1; a(1) = 2$, etc. Please mention this in your answer if you choose to use this.
Test cases
Input | Output
---------------
1 | 1
5 | 7
20 | 20
50 | 136
78 | 30
123 | 3194
1234 | 8212236486
3000 | 814
9999 | 108240
29890 | 637
It might be fun to know that the largest $a(n)$ for $1le nle32767$ is $a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) lfloor 2 varphirfloor + F(255).$
Rules
- Input and output are integers
- Your program should at least support input in the range of 1 up to 32767). Note that $a(n)$ goes up to 30 digit numbers in this range...
- Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
- Default I/O rules apply.
Default loopholes are forbidden.- This is code-golf, so the shortest answers in bytes wins
code-golf sequence
$endgroup$
Introduction (may be ignored)
Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fifth challenge in this series (links to the first, second, third and fourth challenge).
In this challenge, we will meet the Wythoff array, which is a intertwined avalanche of Fibonacci sequences and Beatty sequences!
The Fibonacci numbers are probably for most of you a well known sequence. Given two starting numbers $F_0$ and $F_1$, the following $F_n$ are given by: $F_n = F_(n-1) + F_(n-2)$ for $n>2$.
The Beatty sequence, given a parameter $r$ is: $B^r_n = lfloor rn rfloor$ for $n ge 1$. One of the properties of the Beatty sequence is that for every parameter $r$, there is exactly one parameter $s=r/(r-1)$, such that the Beatty sequences for those parameters are disjunct and joined together, they span all natural numbers excluding 0 (e.g.: $B^r cup B^r/(r-1) = BbbN setminus 0$).
Now here comes the mindblowing part: you can create an array, where each row is a Fibonacci sequence and each column is a Beatty sequence. This array is the Wythoff array. The best part is: every positive number appears exactly once in this array! The array looks like this:
1 2 3 5 8 13 21 34 55 89 144 ...
4 7 11 18 29 47 76 123 199 322 521 ...
6 10 16 26 42 68 110 178 288 466 754 ...
9 15 24 39 63 102 165 267 432 699 1131 ...
12 20 32 52 84 136 220 356 576 932 1508 ...
14 23 37 60 97 157 254 411 665 1076 1741 ...
17 28 45 73 118 191 309 500 809 1309 2118 ...
19 31 50 81 131 212 343 555 898 1453 2351 ...
22 36 58 94 152 246 398 644 1042 1686 2728 ...
25 41 66 107 173 280 453 733 1186 1919 3105 ...
27 44 71 115 186 301 487 788 1275 2063 3338 ...
...
An element at row $m$ and column $n$ is defined as:
$A_m,n = begincases
leftlfloor lfloor mvarphi rfloor varphi rightrfloor & text if n=1\
leftlfloor lfloor mvarphi rfloor varphi^2 rightrfloor & text if n=2\
A_m,n-2+A_m,n-1 & text if n > 2
endcases$
where $varphi$ is the golden ratio: $varphi=frac1+sqrt52$.
If we follow the anti-diagonals of this array, we get A035513, which is the target sequence for this challenge (note that this sequence is added to the OEIS by Neil Sloane himself!). Since this is a "pure sequence" challenge, the task is to output $a(n)$ for a given $n$ as input, where $a(n)$ is A035513.
There are different strategies you can follow to get to $a(n)$, which makes this challenge (in my opinion) really interesting.
Task
Given an integer input $n$, output $a(n)$ in integer format, where $a(n)$ is A035513.
Note: 1-based indexing is assumed here; you may use 0-based indexing, so $a(0) = 1; a(1) = 2$, etc. Please mention this in your answer if you choose to use this.
Test cases
Input | Output
---------------
1 | 1
5 | 7
20 | 20
50 | 136
78 | 30
123 | 3194
1234 | 8212236486
3000 | 814
9999 | 108240
29890 | 637
It might be fun to know that the largest $a(n)$ for $1le nle32767$ is $a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) lfloor 2 varphirfloor + F(255).$
Rules
- Input and output are integers
- Your program should at least support input in the range of 1 up to 32767). Note that $a(n)$ goes up to 30 digit numbers in this range...
- Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
- Default I/O rules apply.
Default loopholes are forbidden.- This is code-golf, so the shortest answers in bytes wins
code-golf sequence
code-golf sequence
edited Apr 15 at 20:14
agtoever
asked Apr 14 at 21:01
agtoeveragtoever
1,408425
1,408425
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
1
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58
|
show 7 more comments
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
1
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58
2
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
2
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
1
1
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
1
1
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58
|
show 7 more comments
5 Answers
5
active
oldest
votes
$begingroup$
Jelly, 27 24 bytes
p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/
Try it online!
Monadic link using 1-based indexing.
Thanks to @JonathanAllan for a better way of getting the row and columns from n
and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.
Explanation
p` | Cartesian product of the range from 1..input with itself
SÞ | Sort by sum
⁸ị | Find the tuple at the position indicated by the input - this is the row and column
ð ð/ | Start a new dyadic chain using the row as the left and column as the right argument
’ | Increase the row by 1
; ¥ | Concatenate to:
×Øp | row × φ
Ḟ | rounded down
× ¤ | Multiply this pair by
ÆḞ | the Fibonacci numbers at positions
⁹ | column index and
r‘ | column index plus one
S | sum
Note this is based on the description of the Python code on the OEIS page.
$endgroup$
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
Apr 14 at 23:32
add a comment |
$begingroup$
R, 143 130 124 123 bytes
function(n)k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]
Try it online!
Uses the formula $T(n,-1)=n-1; T(n,0)=lfloor ncdotphirfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ to construct the array (transposed), then splits
the array along antidiagonals. k
merely exists to prevent forcing a drop=F
argument in m[-1:-2,]
for the case n=1
.
Thanks to Neil for pointing out a 1 byte golf.
R, 150 138 132 bytes
function(n)T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]
Try it online!
Implements the formula $T(n,k)=Fib(k+1)cdotlfloor ncdotphirfloor+Fib(k)cdot(n-1)$ to get generate the array, then splits
along the antidiagonals and extracts the nth
element.
Thanks to Robin Ryder for the T[2]=1
trick for generating the Fibonacci sequence.
Both solutions are highly inefficient, creating an nxn
matrix of (most likely) double
s, as R promotes integer
(32-bit signed) to double
automatically when overflowing, but the second one should be quite a lot faster. Taking n
as a bignum should work automatically, using the call gmp::as.bigz(n)
, should loss of precision under double
s be worrisome, and then the language would be R + gmp
.
$endgroup$
$begingroup$
Can you use(1+5^.5)/2
instead of(.5+5^.5/2)
?
$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 90 bytes
Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,b,#,a,b,1,-1]][[#]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Jelly, 30 bytes
p`SÞ⁸ịð;Øp,²;¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/
Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ
(double, square-root, ceiling) like in this test-suite.
$endgroup$
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
add a comment |
$begingroup$
Charcoal, 54 bytes
Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ
Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:
Nθ
Input q
.
≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»
Calculate the antidiagonal by subtracting ever increasing numbers from q
, which ends up with the target row number m
.
⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι
Calculate the first m+1
terms of A019446, although we're only interested in the m
th.
⊞υθF⁺²⁻θη⊞υΣ…⮌υ²
Calculate the first n+4
terms of the generalised Fibonacci series that starts with [a(m), m]
. The terms of this sequence are the m
th terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the m
th row of the array.
I⊟υ
Output the desired term.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183186%2fnew-order-5-where-fibonacci-and-beatty-meet-at-wythoff%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Jelly, 27 24 bytes
p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/
Try it online!
Monadic link using 1-based indexing.
Thanks to @JonathanAllan for a better way of getting the row and columns from n
and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.
Explanation
p` | Cartesian product of the range from 1..input with itself
SÞ | Sort by sum
⁸ị | Find the tuple at the position indicated by the input - this is the row and column
ð ð/ | Start a new dyadic chain using the row as the left and column as the right argument
’ | Increase the row by 1
; ¥ | Concatenate to:
×Øp | row × φ
Ḟ | rounded down
× ¤ | Multiply this pair by
ÆḞ | the Fibonacci numbers at positions
⁹ | column index and
r‘ | column index plus one
S | sum
Note this is based on the description of the Python code on the OEIS page.
$endgroup$
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
Apr 14 at 23:32
add a comment |
$begingroup$
Jelly, 27 24 bytes
p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/
Try it online!
Monadic link using 1-based indexing.
Thanks to @JonathanAllan for a better way of getting the row and columns from n
and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.
Explanation
p` | Cartesian product of the range from 1..input with itself
SÞ | Sort by sum
⁸ị | Find the tuple at the position indicated by the input - this is the row and column
ð ð/ | Start a new dyadic chain using the row as the left and column as the right argument
’ | Increase the row by 1
; ¥ | Concatenate to:
×Øp | row × φ
Ḟ | rounded down
× ¤ | Multiply this pair by
ÆḞ | the Fibonacci numbers at positions
⁹ | column index and
r‘ | column index plus one
S | sum
Note this is based on the description of the Python code on the OEIS page.
$endgroup$
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
Apr 14 at 23:32
add a comment |
$begingroup$
Jelly, 27 24 bytes
p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/
Try it online!
Monadic link using 1-based indexing.
Thanks to @JonathanAllan for a better way of getting the row and columns from n
and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.
Explanation
p` | Cartesian product of the range from 1..input with itself
SÞ | Sort by sum
⁸ị | Find the tuple at the position indicated by the input - this is the row and column
ð ð/ | Start a new dyadic chain using the row as the left and column as the right argument
’ | Increase the row by 1
; ¥ | Concatenate to:
×Øp | row × φ
Ḟ | rounded down
× ¤ | Multiply this pair by
ÆḞ | the Fibonacci numbers at positions
⁹ | column index and
r‘ | column index plus one
S | sum
Note this is based on the description of the Python code on the OEIS page.
$endgroup$
Jelly, 27 24 bytes
p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/
Try it online!
Monadic link using 1-based indexing.
Thanks to @JonathanAllan for a better way of getting the row and columns from n
and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.
Explanation
p` | Cartesian product of the range from 1..input with itself
SÞ | Sort by sum
⁸ị | Find the tuple at the position indicated by the input - this is the row and column
ð ð/ | Start a new dyadic chain using the row as the left and column as the right argument
’ | Increase the row by 1
; ¥ | Concatenate to:
×Øp | row × φ
Ḟ | rounded down
× ¤ | Multiply this pair by
ÆḞ | the Fibonacci numbers at positions
⁹ | column index and
r‘ | column index plus one
S | sum
Note this is based on the description of the Python code on the OEIS page.
edited Apr 15 at 0:16
answered Apr 14 at 22:54
Nick KennedyNick Kennedy
1,83149
1,83149
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
Apr 14 at 23:32
add a comment |
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
Apr 14 at 23:32
1
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)$endgroup$
– Jonathan Allan
Apr 14 at 23:32
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)$endgroup$
– Jonathan Allan
Apr 14 at 23:32
add a comment |
$begingroup$
R, 143 130 124 123 bytes
function(n)k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]
Try it online!
Uses the formula $T(n,-1)=n-1; T(n,0)=lfloor ncdotphirfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ to construct the array (transposed), then splits
the array along antidiagonals. k
merely exists to prevent forcing a drop=F
argument in m[-1:-2,]
for the case n=1
.
Thanks to Neil for pointing out a 1 byte golf.
R, 150 138 132 bytes
function(n)T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]
Try it online!
Implements the formula $T(n,k)=Fib(k+1)cdotlfloor ncdotphirfloor+Fib(k)cdot(n-1)$ to get generate the array, then splits
along the antidiagonals and extracts the nth
element.
Thanks to Robin Ryder for the T[2]=1
trick for generating the Fibonacci sequence.
Both solutions are highly inefficient, creating an nxn
matrix of (most likely) double
s, as R promotes integer
(32-bit signed) to double
automatically when overflowing, but the second one should be quite a lot faster. Taking n
as a bignum should work automatically, using the call gmp::as.bigz(n)
, should loss of precision under double
s be worrisome, and then the language would be R + gmp
.
$endgroup$
$begingroup$
Can you use(1+5^.5)/2
instead of(.5+5^.5/2)
?
$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
add a comment |
$begingroup$
R, 143 130 124 123 bytes
function(n)k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]
Try it online!
Uses the formula $T(n,-1)=n-1; T(n,0)=lfloor ncdotphirfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ to construct the array (transposed), then splits
the array along antidiagonals. k
merely exists to prevent forcing a drop=F
argument in m[-1:-2,]
for the case n=1
.
Thanks to Neil for pointing out a 1 byte golf.
R, 150 138 132 bytes
function(n)T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]
Try it online!
Implements the formula $T(n,k)=Fib(k+1)cdotlfloor ncdotphirfloor+Fib(k)cdot(n-1)$ to get generate the array, then splits
along the antidiagonals and extracts the nth
element.
Thanks to Robin Ryder for the T[2]=1
trick for generating the Fibonacci sequence.
Both solutions are highly inefficient, creating an nxn
matrix of (most likely) double
s, as R promotes integer
(32-bit signed) to double
automatically when overflowing, but the second one should be quite a lot faster. Taking n
as a bignum should work automatically, using the call gmp::as.bigz(n)
, should loss of precision under double
s be worrisome, and then the language would be R + gmp
.
$endgroup$
$begingroup$
Can you use(1+5^.5)/2
instead of(.5+5^.5/2)
?
$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
add a comment |
$begingroup$
R, 143 130 124 123 bytes
function(n)k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]
Try it online!
Uses the formula $T(n,-1)=n-1; T(n,0)=lfloor ncdotphirfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ to construct the array (transposed), then splits
the array along antidiagonals. k
merely exists to prevent forcing a drop=F
argument in m[-1:-2,]
for the case n=1
.
Thanks to Neil for pointing out a 1 byte golf.
R, 150 138 132 bytes
function(n)T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]
Try it online!
Implements the formula $T(n,k)=Fib(k+1)cdotlfloor ncdotphirfloor+Fib(k)cdot(n-1)$ to get generate the array, then splits
along the antidiagonals and extracts the nth
element.
Thanks to Robin Ryder for the T[2]=1
trick for generating the Fibonacci sequence.
Both solutions are highly inefficient, creating an nxn
matrix of (most likely) double
s, as R promotes integer
(32-bit signed) to double
automatically when overflowing, but the second one should be quite a lot faster. Taking n
as a bignum should work automatically, using the call gmp::as.bigz(n)
, should loss of precision under double
s be worrisome, and then the language would be R + gmp
.
$endgroup$
R, 143 130 124 123 bytes
function(n)k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]
Try it online!
Uses the formula $T(n,-1)=n-1; T(n,0)=lfloor ncdotphirfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ to construct the array (transposed), then splits
the array along antidiagonals. k
merely exists to prevent forcing a drop=F
argument in m[-1:-2,]
for the case n=1
.
Thanks to Neil for pointing out a 1 byte golf.
R, 150 138 132 bytes
function(n)T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]
Try it online!
Implements the formula $T(n,k)=Fib(k+1)cdotlfloor ncdotphirfloor+Fib(k)cdot(n-1)$ to get generate the array, then splits
along the antidiagonals and extracts the nth
element.
Thanks to Robin Ryder for the T[2]=1
trick for generating the Fibonacci sequence.
Both solutions are highly inefficient, creating an nxn
matrix of (most likely) double
s, as R promotes integer
(32-bit signed) to double
automatically when overflowing, but the second one should be quite a lot faster. Taking n
as a bignum should work automatically, using the call gmp::as.bigz(n)
, should loss of precision under double
s be worrisome, and then the language would be R + gmp
.
edited 2 days ago
answered Apr 15 at 0:55
GiuseppeGiuseppe
17.9k31153
17.9k31153
$begingroup$
Can you use(1+5^.5)/2
instead of(.5+5^.5/2)
?
$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
add a comment |
$begingroup$
Can you use(1+5^.5)/2
instead of(.5+5^.5/2)
?
$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
Can you use
(1+5^.5)/2
instead of (.5+5^.5/2)
?$endgroup$
– Neil
2 days ago
$begingroup$
Can you use
(1+5^.5)/2
instead of (.5+5^.5/2)
?$endgroup$
– Neil
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
@Neil ...yes, I can. Thank you! Only going to edit it into the top one unless I can find a way to golf down the second one quite a lot more.
$endgroup$
– Giuseppe
2 days ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 90 bytes
Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,b,#,a,b,1,-1]][[#]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 90 bytes
Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,b,#,a,b,1,-1]][[#]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 90 bytes
Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,b,#,a,b,1,-1]][[#]]&
Try it online!
$endgroup$
Wolfram Language (Mathematica), 90 bytes
Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,b,#,a,b,1,-1]][[#]]&
Try it online!
answered Apr 14 at 21:47
J42161217J42161217
14.2k21353
14.2k21353
add a comment |
add a comment |
$begingroup$
Jelly, 30 bytes
p`SÞ⁸ịð;Øp,²;¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/
Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ
(double, square-root, ceiling) like in this test-suite.
$endgroup$
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
add a comment |
$begingroup$
Jelly, 30 bytes
p`SÞ⁸ịð;Øp,²;¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/
Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ
(double, square-root, ceiling) like in this test-suite.
$endgroup$
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
add a comment |
$begingroup$
Jelly, 30 bytes
p`SÞ⁸ịð;Øp,²;¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/
Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ
(double, square-root, ceiling) like in this test-suite.
$endgroup$
Jelly, 30 bytes
p`SÞ⁸ịð;Øp,²;¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/
Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ
(double, square-root, ceiling) like in this test-suite.
edited Apr 14 at 23:16
answered Apr 14 at 22:50
Jonathan AllanJonathan Allan
54.5k537174
54.5k537174
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
add a comment |
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
2
2
$begingroup$
you are right!
740496902
is the result for 999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
you are right!
740496902
is the result for 999
$endgroup$
– J42161217
Apr 14 at 22:54
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
Combining the first part of yours and second part of mine gives 25 bytes. Not sure which of us should have the combined version!
$endgroup$
– Nick Kennedy
Apr 14 at 23:05
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
Apr 14 at 23:07
add a comment |
$begingroup$
Charcoal, 54 bytes
Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ
Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:
Nθ
Input q
.
≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»
Calculate the antidiagonal by subtracting ever increasing numbers from q
, which ends up with the target row number m
.
⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι
Calculate the first m+1
terms of A019446, although we're only interested in the m
th.
⊞υθF⁺²⁻θη⊞υΣ…⮌υ²
Calculate the first n+4
terms of the generalised Fibonacci series that starts with [a(m), m]
. The terms of this sequence are the m
th terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the m
th row of the array.
I⊟υ
Output the desired term.
$endgroup$
add a comment |
$begingroup$
Charcoal, 54 bytes
Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ
Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:
Nθ
Input q
.
≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»
Calculate the antidiagonal by subtracting ever increasing numbers from q
, which ends up with the target row number m
.
⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι
Calculate the first m+1
terms of A019446, although we're only interested in the m
th.
⊞υθF⁺²⁻θη⊞υΣ…⮌υ²
Calculate the first n+4
terms of the generalised Fibonacci series that starts with [a(m), m]
. The terms of this sequence are the m
th terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the m
th row of the array.
I⊟υ
Output the desired term.
$endgroup$
add a comment |
$begingroup$
Charcoal, 54 bytes
Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ
Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:
Nθ
Input q
.
≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»
Calculate the antidiagonal by subtracting ever increasing numbers from q
, which ends up with the target row number m
.
⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι
Calculate the first m+1
terms of A019446, although we're only interested in the m
th.
⊞υθF⁺²⁻θη⊞υΣ…⮌υ²
Calculate the first n+4
terms of the generalised Fibonacci series that starts with [a(m), m]
. The terms of this sequence are the m
th terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the m
th row of the array.
I⊟υ
Output the desired term.
$endgroup$
Charcoal, 54 bytes
Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ
Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:
Nθ
Input q
.
≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»
Calculate the antidiagonal by subtracting ever increasing numbers from q
, which ends up with the target row number m
.
⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι
Calculate the first m+1
terms of A019446, although we're only interested in the m
th.
⊞υθF⁺²⁻θη⊞υΣ…⮌υ²
Calculate the first n+4
terms of the generalised Fibonacci series that starts with [a(m), m]
. The terms of this sequence are the m
th terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the m
th row of the array.
I⊟υ
Output the desired term.
answered 1 hour ago
NeilNeil
83.1k745179
83.1k745179
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183186%2fnew-order-5-where-fibonacci-and-beatty-meet-at-wythoff%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
Apr 14 at 21:03
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
Apr 14 at 21:10
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
Apr 14 at 21:13
1
$begingroup$
Is a floating point representation of phi (or rt(5)) and application of the recurrence going to satisfy the range requirement?
$endgroup$
– Jonathan Allan
Apr 14 at 21:18
1
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
Apr 14 at 22:58