Check if digits in a number can be rearranged to form a fibonacci number
This question is asked in a programming contest. I couldn't find any way other than generating all permutations. But the number of digits is upto 15 and no of permutations (15!) is very large. Is there any other way?
I know that if (5*N^2 + 4) or (5*N^2 - 4) is a perfect square, n is fibonacci.
string algorithm fibonacci
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
add a comment |
This question is asked in a programming contest. I couldn't find any way other than generating all permutations. But the number of digits is upto 15 and no of permutations (15!) is very large. Is there any other way?
I know that if (5*N^2 + 4) or (5*N^2 - 4) is a perfect square, n is fibonacci.
string algorithm fibonacci
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
1
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07
add a comment |
This question is asked in a programming contest. I couldn't find any way other than generating all permutations. But the number of digits is upto 15 and no of permutations (15!) is very large. Is there any other way?
I know that if (5*N^2 + 4) or (5*N^2 - 4) is a perfect square, n is fibonacci.
string algorithm fibonacci
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
This question is asked in a programming contest. I couldn't find any way other than generating all permutations. But the number of digits is upto 15 and no of permutations (15!) is very large. Is there any other way?
I know that if (5*N^2 + 4) or (5*N^2 - 4) is a perfect square, n is fibonacci.
string algorithm fibonacci
string algorithm fibonacci
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
edited Nov 14 '18 at 10:29
Deduplicator
34.6k64889
34.6k64889
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
asked Nov 14 '18 at 9:44
duplex143duplex143
162113
162113
1
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07
add a comment |
1
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07
1
1
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07
add a comment |
1 Answer
1
active
oldest
votes
You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
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: "1"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fstackoverflow.com%2fquestions%2f53297138%2fcheck-if-digits-in-a-number-can-be-rearranged-to-form-a-fibonacci-number%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
add a comment |
You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
add a comment |
You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
answered Nov 14 '18 at 9:55
Martin HeraleckýMartin Heralecký
3,15421134
3,15421134
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
add a comment |
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
I didn't know that Fibonacci sequence increases so drastically. Exponential growth I think. Thanks.
– duplex143
Nov 14 '18 at 10:01
1
1
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
Yes, inverting the direction can make for a surprising jump in efficiency.
– Deduplicator
Nov 14 '18 at 10:04
1
1
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
Upvoted. As a note, the fibonacci numbers grow at a rate of phi (~= 1.618). Since phi**5 > 10, there can never be more than 5 Fibonacci numbers with the same digit length (except for digit length 1).
– Paul Hankin
Nov 14 '18 at 14:02
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2fstackoverflow.com%2fquestions%2f53297138%2fcheck-if-digits-in-a-number-can-be-rearranged-to-form-a-fibonacci-number%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
1
As an aside, assuming you work in base-10, there are far fewer than 15! permutations of any 15-digit number.
– Deduplicator
Nov 14 '18 at 10:06
Yes. 15! divided the product of the factorial of the no of repeating numbers.
– duplex143
Nov 14 '18 at 10:07