3
\$\begingroup\$

This question already has an answer here:

Write a program or function that takes an input greater than or equal to 2. It should output a truthy or falsy value corresponding to whether the input is a Lucas number or not. You may take input from STDIN, or whichever source is most suitable to you.

This question is different to this one because this question is specifically for Lucas numbers only, and not Fibonacci numbers at all, whereas that question was Lucas number, Fibonacci numbers and both possible combinations of them. This question was, however, inspired by that question and is similar in some regards.

Lucas numbers are the numbers that result from the rules following: the first Lucas number is a 2, the second is a 1, and each term after that is the sum of the previous two. Yes, it is very similar to the Fibonacci sequence, but this has the added advantage of converging closer to the golden ratio, phi, faster than Fibonacci numbers do.

Example inputs/outputs

Input   Output
--------------
3       True
4       True
7       True
8      False
10     False
3421   False
9349    True

etc.

Some limitations

  • Your program/function must run in a reasonable amount of time. It should terminate within seconds and minutes, not hours and days.
  • Your program must not calculate all the Lucas numbers up to the input number

This is code golf, so the shortest code in bytes wins.

\$\endgroup\$

marked as duplicate by Blue, Morgan Thrapp, AdmBorkBork, Addison Crump, Alex A. code-golf Apr 1 '16 at 21:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    \$\begingroup\$ This is a subtask of this challenge. \$\endgroup\$ – Alex A. Apr 1 '16 at 20:50
  • \$\begingroup\$ Yup. I was heavily inspired by that one. \$\endgroup\$ – mriklojn Apr 1 '16 at 21:06
2
\$\begingroup\$

MATL, 19 17 16 18 bytes

2^5*20t_h+X^Xj1\~a

Try it Online!

Explanation

2^          % Implicitly grab the input and square it
5*          % Multiply the result by 5
20          % Create the literal number 20
t_          % Duplicate and negate the second 20
h           % Concatenate 20 and -20 to get [20 -20]
+           % Add the array to the result of 5*n^2
X^          % Compute the square root
Xj          % Ensure that the result is a real number
1\          % Compute the remainder to test for perfect squares
~a          % Check to see if any had a remainder of zero (returns a boolean)
\$\endgroup\$
1
\$\begingroup\$

Python, 69 67 53 characters

lambda x:0in(((5*x**2+20)**.5)%1,((5*x**2-20)**.5)%1)

This works in both Python 2.x and 3.x.

See this answer to see how it works - n is a Lucas number if either 5n^2+20 or 5n^2-20 is a perfect square. My program checks to see if either of their square roots are integers and checks if 0 is in the tuple that results.

\$\endgroup\$
1
\$\begingroup\$

MATLAB, 43 bytes

@(n)~all(rem(real(sqrt(5*n^2+[-20 20])),1))

Inspired by Anders Kaseorg's answer

\$\endgroup\$
1
\$\begingroup\$

Python, 45 43 characters

lambda n:0in[(5*n*n+k)**.5%1for k in-20,20]

Based on a proof given here.

\$\endgroup\$
  • \$\begingroup\$ I knew there was a shorter way in Python! Your answer has given me insight in golfing, as I am relatively new to this art. Thanks. \$\endgroup\$ – mriklojn Apr 1 '16 at 21:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.