New Order #5: where Fibonacci and Beatty meet at Wythoff Announcing the arrival of Valued...
What is the musical term for a note that continously plays through a melody?
Storing hydrofluoric acid before the invention of plastics
Models of set theory where not every set can be linearly ordered
Why one of virtual NICs called bond0?
Gastric acid as a weapon
Why aren't air breathing engines used as small first stages
When is phishing education going too far?
What are the pros and cons of Aerospike nosecones?
How can I make names more distinctive without making them longer?
Is the address of a local variable a constexpr?
Is it true to say that an hosting provider's DNS server is what links the entire hosting environment to ICANN?
Is it true that "carbohydrates are of no use for the basal metabolic need"?
What are 'alternative tunings' of a guitar and why would you use them? Doesn't it make it more difficult to play?
List *all* the tuples!
Is the Standard Deduction better than Itemized when both are the same amount?
ListPlot join points by nearest neighbor rather than order
Do you forfeit tax refunds/credits if you aren't required to and don't file by April 15?
Antler Helmet: Can it work?
How do I mention the quality of my school without bragging
How does cp -a work
Are my PIs rude or am I just being too sensitive?
How discoverable are IPv6 addresses and AAAA names by potential attackers?
Should I call the interviewer directly, if HR aren't responding?
Is there a Spanish version of "dot your i's and cross your t's" that includes the letter 'ñ'?
New Order #5: where Fibonacci and Beatty meet at Wythoff
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 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)} = Bbb{N} 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} = begin{cases}
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
end{cases}$
where $varphi$ is the golden ratio: $varphi=frac{1+sqrt{5}}{2}$.
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)} = Bbb{N} 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} = begin{cases}
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
end{cases}$
where $varphi$ is the golden ratio: $varphi=frac{1+sqrt{5}}{2}$.
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
yesterday
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
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
yesterday
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
yesterday
|
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)} = Bbb{N} 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} = begin{cases}
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
end{cases}$
where $varphi$ is the golden ratio: $varphi=frac{1+sqrt{5}}{2}$.
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)} = Bbb{N} 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} = begin{cases}
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
end{cases}$
where $varphi$ is the golden ratio: $varphi=frac{1+sqrt{5}}{2}$.
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 6 hours ago
agtoever
asked yesterday
agtoeveragtoever
1,410425
1,410425
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
yesterday
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
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
yesterday
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
yesterday
|
show 7 more comments
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
yesterday
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
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
yesterday
1
$begingroup$
Please fix the 9th test case : it is999
not9999
$endgroup$
– J42161217
yesterday
2
2
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
yesterday
$begingroup$
So what's the New Order reference here?
$endgroup$
– Luis Mendo
yesterday
2
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
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
yesterday
$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
yesterday
1
1
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
yesterday
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
yesterday
|
show 7 more comments
4 Answers
4
active
oldest
votes
$begingroup$
R, 143 130 124 bytes
function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(.5+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
.
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$
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
yesterday
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
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
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
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
R, 143 130 124 bytes
function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(.5+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
.
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$
add a comment |
$begingroup$
R, 143 130 124 bytes
function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(.5+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
.
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$
add a comment |
$begingroup$
R, 143 130 124 bytes
function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(.5+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
.
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 bytes
function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(.5+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
.
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 8 hours ago
answered yesterday
GiuseppeGiuseppe
17.8k31153
17.8k31153
add a comment |
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
yesterday
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
yesterday
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 yesterday
answered yesterday
Nick KennedyNick Kennedy
1,67649
1,67649
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
yesterday
add a comment |
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)
$endgroup$
– Jonathan Allan
yesterday
1
1
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)$endgroup$
– Jonathan Allan
yesterday
$begingroup$
...×⁹r‘ÆḞ¤Sð/
saves one in your amalgamation version (TIO)$endgroup$
– Jonathan Allan
yesterday
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 yesterday
J42161217J42161217
14k21353
14k21353
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
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
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
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
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 yesterday
answered yesterday
Jonathan AllanJonathan Allan
54.4k537174
54.4k537174
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
add a comment |
2
$begingroup$
you are right!740496902
is the result for999
$endgroup$
– J42161217
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
2
2
$begingroup$
you are right!
740496902
is the result for 999
$endgroup$
– J42161217
yesterday
$begingroup$
you are right!
740496902
is the result for 999
$endgroup$
– J42161217
yesterday
$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
yesterday
$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
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
$begingroup$
@NickKennedy - nice, go for it!
$endgroup$
– Jonathan Allan
yesterday
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
yesterday
2
$begingroup$
@LuisMendo: the avalanche of Fibonacci and Beatty sequences, which form the Wythoff array...
$endgroup$
– agtoever
yesterday
$begingroup$
Ah, I completely missed that! Now I feel regret...
$endgroup$
– Luis Mendo
yesterday
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
yesterday
1
$begingroup$
Please fix the 9th test case : it is
999
not9999
$endgroup$
– J42161217
yesterday