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

asked 3 hours ago

Cowabunghole

708316

add a commentÂ |Â

up vote
4
down vote

favorite

Background

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

asked 3 hours ago

Cowabunghole

708316

add a commentÂ |Â

up vote
4
down vote

favorite

Background

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

asked 3 hours ago

Cowabunghole

708316

Background

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

asked 3 hours ago

Cowabunghole

708316

asked 3 hours ago

Cowabunghole

708316

asked 3 hours ago

Cowabunghole

708316

asked 3 hours ago

Cowabunghole

708316

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Â |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

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',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

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

Name

3 Answers
3

active

oldest

votes

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
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

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

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

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

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

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

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Category

Random preview

Is this number secretly Fibonacci?

Background

Notes

Challenge

Input

Output

Scoring

Test Cases

Background

Notes

Challenge

Input

Output

Scoring

Test Cases

Background

Notes

Challenge

Input

Output

Scoring

Test Cases

Background

Notes

Challenge

Input

Output

Scoring

Test Cases

3 Answers 3

JavaScript (Node.js), 54 bytes

R, 83 bytes

Jelly, 15 bytes

How?

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

JavaScript (Node.js), 54 bytes

JavaScript (Node.js), 54 bytes

JavaScript (Node.js), 54 bytes

JavaScript (Node.js), 54 bytes

R, 83 bytes

R, 83 bytes

R, 83 bytes

R, 83 bytes

Jelly, 15 bytes

How?

Jelly, 15 bytes

How?

Jelly, 15 bytes

How?

Jelly, 15 bytes

How?

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor