Mixing
Is this number secretly Fibonacci?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Background
Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer n is itself a Fibonacci number, we will call n "secretly" Fibonacci.
For example:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Notes
- The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number <= n and subtract it from n until you reach 0
- All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.
Challenge
Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.
Input
You may take input in any reasonable format. You may assume the input will be a single positive integer.
Output
Output one of two distinct results for whether the input is secretly Fibonacci. Examples include True/False, 1/0, etc.
Scoring
This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.
Test Cases
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
code-golf decision-problem fibonacci
asked 3 hours ago
Cowabunghole
708316
add a comment |Â
up vote
4
down vote
favorite
Background
Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer n is itself a Fibonacci number, we will call n "secretly" Fibonacci.
For example:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Notes
- The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number <= n and subtract it from n until you reach 0
- All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.
Challenge
Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.
Input
You may take input in any reasonable format. You may assume the input will be a single positive integer.
Output
Output one of two distinct results for whether the input is secretly Fibonacci. Examples include True/False, 1/0, etc.
Scoring
This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.
Test Cases
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
code-golf decision-problem fibonacci
asked 3 hours ago
Cowabunghole
708316
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Background
Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer n is itself a Fibonacci number, we will call n "secretly" Fibonacci.
For example:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Notes
- The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number <= n and subtract it from n until you reach 0
- All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.
Challenge
Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.
Input
You may take input in any reasonable format. You may assume the input will be a single positive integer.
Output
Output one of two distinct results for whether the input is secretly Fibonacci. Examples include True/False, 1/0, etc.
Scoring
This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.
Test Cases
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
code-golf decision-problem fibonacci
asked 3 hours ago
Cowabunghole
708316
Background
Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer n is itself a Fibonacci number, we will call n "secretly" Fibonacci.
For example:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Notes
- The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number <= n and subtract it from n until you reach 0
- All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.
Challenge
Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.
Input
You may take input in any reasonable format. You may assume the input will be a single positive integer.
Output
Output one of two distinct results for whether the input is secretly Fibonacci. Examples include True/False, 1/0, etc.
Scoring
This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.
Test Cases
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
code-golf decision-problem fibonacci
code-golf decision-problem fibonacci
asked 3 hours ago
Cowabunghole
708316
asked 3 hours ago
Cowabunghole
708316
asked 3 hours ago
Cowabunghole
708316
asked 3 hours ago
Cowabunghole
708316
asked 3 hours ago
Cowabunghole
708316
708316
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
JavaScript (Node.js), 54 bytes
x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)
Try it online!
answered 2 hours ago
l4m2
4,0181431
add a comment |Â
up vote
1
down vote
R, 83 bytes
function(n)T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n)n=n-T[T<=n][1]
F=F+1
F%in%T
Try it online!
answered 1 hour ago
Giuseppe
15.5k31051
add a comment |Â
up vote
0
down vote
Jelly, 15 bytes
‘ÆḞ€fRṪạµƬL’ƊâºỊ
A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.
Try it online! (too inefficient for the larger test cases)
How?
‘ÆḞ€fRṪạµƬL’ƊâºỊ - Link: integer, I
µƬ - perform the monadic link to the left as a function of the current I,
- collecting up all the inputs until the results are no longer unique:
‘ - increment I -> I+1
ÆḞ€ - nth Fibonacci number for €ach n in [1,I+1]
R - range from 1 to I
f - filter discard (discard Fibonacci numbers not in the range, i.e. > I)
Ṫ - tail (get the largest)
ạ - absolute difference with I
- This gives us a list from I decreasing by Fibonacci numbers to 0
- e.g. for 88 we get [88,33,12,4,1,0]
- because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
L - length (the number of Fibonacci numbers required plus one)
’ - decrement (the number of Fibonacci numbers required)
Ɗ - treat the last three links (which is everything to the left) as a monad:
⺠- ...and repeat it
- i.e. get the number of Fibonacci numbers required for the number of
- Fibonacci numbers required to represent I.
- This is 1 if I is Secretly Fibonacci, and greater if not)
Ị - insignificant? (is the absolute value of that <= 1?)
answered 25 mins ago
Jonathan Allan
49.5k534163
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
JavaScript (Node.js), 54 bytes
x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)
Try it online!
answered 2 hours ago
l4m2
4,0181431
add a comment |Â
up vote
2
down vote
JavaScript (Node.js), 54 bytes
x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)
Try it online!
answered 2 hours ago
l4m2
4,0181431
add a comment |Â
up vote
2
down vote
up vote
2
down vote
JavaScript (Node.js), 54 bytes
x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)
Try it online!
answered 2 hours ago
l4m2
4,0181431
JavaScript (Node.js), 54 bytes
x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)
Try it online!
answered 2 hours ago
l4m2
4,0181431
answered 2 hours ago
l4m2
4,0181431
answered 2 hours ago
l4m2
4,0181431
answered 2 hours ago
l4m2
4,0181431
4,0181431
add a comment |Â
add a comment |Â
up vote
1
down vote
R, 83 bytes
function(n)T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n)n=n-T[T<=n][1]
F=F+1
F%in%T
Try it online!
answered 1 hour ago
Giuseppe
15.5k31051
add a comment |Â
up vote
1
down vote
R, 83 bytes
function(n)T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n)n=n-T[T<=n][1]
F=F+1
F%in%T
Try it online!
answered 1 hour ago
Giuseppe
15.5k31051
add a comment |Â
up vote
1
down vote
up vote
1
down vote
R, 83 bytes
function(n)T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n)n=n-T[T<=n][1]
F=F+1
F%in%T
Try it online!
answered 1 hour ago
Giuseppe
15.5k31051
R, 83 bytes
function(n)T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n)n=n-T[T<=n][1]
F=F+1
F%in%T
Try it online!
answered 1 hour ago
Giuseppe
15.5k31051
answered 1 hour ago
Giuseppe
15.5k31051
answered 1 hour ago
Giuseppe
15.5k31051
answered 1 hour ago
Giuseppe
15.5k31051
15.5k31051
add a comment |Â
add a comment |Â
up vote
0
down vote
Jelly, 15 bytes
‘ÆḞ€fRṪạµƬL’ƊâºỊ
A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.
Try it online! (too inefficient for the larger test cases)
How?
‘ÆḞ€fRṪạµƬL’ƊâºỊ - Link: integer, I
µƬ - perform the monadic link to the left as a function of the current I,
- collecting up all the inputs until the results are no longer unique:
‘ - increment I -> I+1
ÆḞ€ - nth Fibonacci number for €ach n in [1,I+1]
R - range from 1 to I
f - filter discard (discard Fibonacci numbers not in the range, i.e. > I)
Ṫ - tail (get the largest)
ạ - absolute difference with I
- This gives us a list from I decreasing by Fibonacci numbers to 0
- e.g. for 88 we get [88,33,12,4,1,0]
- because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
L - length (the number of Fibonacci numbers required plus one)
’ - decrement (the number of Fibonacci numbers required)
Ɗ - treat the last three links (which is everything to the left) as a monad:
⺠- ...and repeat it
- i.e. get the number of Fibonacci numbers required for the number of
- Fibonacci numbers required to represent I.
- This is 1 if I is Secretly Fibonacci, and greater if not)
Ị - insignificant? (is the absolute value of that <= 1?)
answered 25 mins ago
Jonathan Allan
49.5k534163
add a comment |Â
up vote
0
down vote
Jelly, 15 bytes
‘ÆḞ€fRṪạµƬL’ƊâºỊ
A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.
Try it online! (too inefficient for the larger test cases)
How?
‘ÆḞ€fRṪạµƬL’ƊâºỊ - Link: integer, I
µƬ - perform the monadic link to the left as a function of the current I,
- collecting up all the inputs until the results are no longer unique:
‘ - increment I -> I+1
ÆḞ€ - nth Fibonacci number for €ach n in [1,I+1]
R - range from 1 to I
f - filter discard (discard Fibonacci numbers not in the range, i.e. > I)
Ṫ - tail (get the largest)
ạ - absolute difference with I
- This gives us a list from I decreasing by Fibonacci numbers to 0
- e.g. for 88 we get [88,33,12,4,1,0]
- because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
L - length (the number of Fibonacci numbers required plus one)
’ - decrement (the number of Fibonacci numbers required)
Ɗ - treat the last three links (which is everything to the left) as a monad:
⺠- ...and repeat it
- i.e. get the number of Fibonacci numbers required for the number of
- Fibonacci numbers required to represent I.
- This is 1 if I is Secretly Fibonacci, and greater if not)
Ị - insignificant? (is the absolute value of that <= 1?)
answered 25 mins ago
Jonathan Allan
49.5k534163
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Jelly, 15 bytes
‘ÆḞ€fRṪạµƬL’ƊâºỊ
A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.
Try it online! (too inefficient for the larger test cases)
How?
‘ÆḞ€fRṪạµƬL’ƊâºỊ - Link: integer, I
µƬ - perform the monadic link to the left as a function of the current I,
- collecting up all the inputs until the results are no longer unique:
‘ - increment I -> I+1
ÆḞ€ - nth Fibonacci number for €ach n in [1,I+1]
R - range from 1 to I
f - filter discard (discard Fibonacci numbers not in the range, i.e. > I)
Ṫ - tail (get the largest)
ạ - absolute difference with I
- This gives us a list from I decreasing by Fibonacci numbers to 0
- e.g. for 88 we get [88,33,12,4,1,0]
- because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
L - length (the number of Fibonacci numbers required plus one)
’ - decrement (the number of Fibonacci numbers required)
Ɗ - treat the last three links (which is everything to the left) as a monad:
⺠- ...and repeat it
- i.e. get the number of Fibonacci numbers required for the number of
- Fibonacci numbers required to represent I.
- This is 1 if I is Secretly Fibonacci, and greater if not)
Ị - insignificant? (is the absolute value of that <= 1?)
answered 25 mins ago
Jonathan Allan
49.5k534163
Jelly, 15 bytes
‘ÆḞ€fRṪạµƬL’ƊâºỊ
A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.
Try it online! (too inefficient for the larger test cases)
How?
‘ÆḞ€fRṪạµƬL’ƊâºỊ - Link: integer, I
µƬ - perform the monadic link to the left as a function of the current I,
- collecting up all the inputs until the results are no longer unique:
‘ - increment I -> I+1
ÆḞ€ - nth Fibonacci number for €ach n in [1,I+1]
R - range from 1 to I
f - filter discard (discard Fibonacci numbers not in the range, i.e. > I)
Ṫ - tail (get the largest)
ạ - absolute difference with I
- This gives us a list from I decreasing by Fibonacci numbers to 0
- e.g. for 88 we get [88,33,12,4,1,0]
- because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
L - length (the number of Fibonacci numbers required plus one)
’ - decrement (the number of Fibonacci numbers required)
Ɗ - treat the last three links (which is everything to the left) as a monad:
⺠- ...and repeat it
- i.e. get the number of Fibonacci numbers required for the number of
- Fibonacci numbers required to represent I.
- This is 1 if I is Secretly Fibonacci, and greater if not)
Ị - insignificant? (is the absolute value of that <= 1?)
answered 25 mins ago
Jonathan Allan
49.5k534163
answered 25 mins ago
Jonathan Allan
49.5k534163
answered 25 mins ago
Jonathan Allan
49.5k534163
answered 25 mins ago
Jonathan Allan
49.5k534163
49.5k534163
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174907%2fis-this-number-secretly-fibonacci%23new-answer', 'question_page');
);
Post as a guest
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
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
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