Since Fibonacci numbers and sequences seems like a popular subject for code golf I thought that it might be a fun challenge to code golf with Keith numbers.

So I propose a challenge that is to create a function that takes an integer and gives back a true or false depending on the number is a Keith number or not.

More about Keith numbers

In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a number in the following integer sequence: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, …

Numberphile has a video explaining how to calculate a Keith number. But basically you take the digits of a number. Add them together and then take the last digits of the original number and add them to the sum of the calculation, rinse and repeat. And example to make it clear.

1 + 4 = 5
4 + 5 = 9
5 + 9 = 14


An integer.


True if the number is a Keith number. False if it's not..

  • \$\begingroup\$ Strictly speaking, "an integer" can include zero or negative numbers. I'm pretty sure neither can be a Keith Number. Do we need to account for this? \$\endgroup\$
    – Iszi
    Nov 14, 2013 at 19:55
  • \$\begingroup\$ Depending on your solution single digit numbers could show up as true. So you should check for potential errors in input. \$\endgroup\$ Nov 15, 2013 at 8:49
  • \$\begingroup\$ Does it have to output true / false or can it be anything truthy/falsey? \$\endgroup\$
    – Cyoce
    Oct 10, 2016 at 0:49

16 Answers 16


GolfScript (31 25 chars)


Input as an integer on top of the stack. Output is 0 (false) or 1 (true). Online demo which lists the Keith numbers up to 100.

  • \$\begingroup\$ Nice idea with the 0>. Unfortunately I can +1 only once. \$\endgroup\$
    – Howard
    Dec 30, 2012 at 8:00

Python (78 75)

while a>n[0]:n=n[1:]+[sum(n)]

n=n[1:]+[sum(n)] does all the magic. It takes every item but the first item of n, sticks on the sum of n (with the first item), then sets that to n.

I wish you could call list on an integer and have the digits seperated.

Returns False on all inputs below 10. Can be 8 characters shorter if it returned True.

  • \$\begingroup\$ You may save two chars if you compare with n[0] instead of n[-1]. \$\endgroup\$
    – Howard
    Dec 28, 2012 at 18:10
  • \$\begingroup\$ Save five more with print 9<a==n[0]. \$\endgroup\$
    – r.e.s.
    Nov 14, 2013 at 3:32
  • \$\begingroup\$ n=n[1:]+[sum(n)] can become n=n[1:]+sum(n), \$\endgroup\$
    – Cyoce
    Oct 10, 2016 at 0:57

GolfScript, 32 29 characters


A GolfScript implementation which can be tested online. Input is given as top element on the stack and it returns 0 (i.e. false) or 1 respectively.

  • \$\begingroup\$ @PeterTaylor Look at the link provided where I did exactly that - and it works... \$\endgroup\$
    – Howard
    Dec 29, 2012 at 19:12
  • \$\begingroup\$ @PeterTaylor Looking at your solution I even could reduce the number of chars further in my approach. \$\endgroup\$
    – Howard
    Dec 29, 2012 at 19:20
  • \$\begingroup\$ I must have not refreshed, because my comment is applicable to version 1. \$\endgroup\$ Dec 29, 2012 at 20:14

APL, 36 34 39 36 33 29 27


Output 1 if Keith, 0 otherwise

GolfScript strikes again!!



Using Right-reduction (⊢/) instead of Take minus 1 (¯1↑), directly saving 1 char and indirectly saves 1 from Disclose ()


⍎¨⍕x←⎕ takes evaluated input (treated as a number) and assign it to x. Converts it to a character array (aka "string" in other languages), and loop through each character (digit), converting it to a number. So this results in a numerical array of the digits.

{(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x} is the main "loop" function:
+/⍵↑⍨-⍴⍕x takes the last ⍴⍕x (no. of digits in x) numbers from the array and sums them.
⍵, concatenates it to the end of the array.
(x>⊢/⍵) check if the last number on the array (which doesn't have +/⍵↑⍨-⍴⍕x concatenated yet) is smaller than x and returns 1 or 0
∇⍣ executes this function on the new array that many times. So if the last number is smaller than x, this function recurs. Otherwise just return the new array

After the executing the function, the array contains the sums up to the point where 2 of the numbers are greater than or equal to x (e.g. 14 will generate 1 4 5 9 14 23, 13 will generate 1 3 4 7 11 18 29)
Finally check if each number is equal to x and output the sum of the resulting binary array.



Added 2 chars :-( to make output 0 if the input is one-digit

Yet another edit



The function now drops the first number (1↓) from the array instead of taking the last ⍴⍕x (↑⍨-⍴⍕x).
However, this approach makes 1= not adequate to handle single digit numbers. So it now drops the last number from the array before checking equality to x, adding 1 char

You guessed it: EDIT


Compares x to the newly-added item instead of the old last item, so dropping the first (instead of last) item before checking equality to x is suffice, saving a minus sign. Saves another 3 by using another form of the Power operator()

And a 25-char gs answer appears (Orz)

Last edit


Can't believe I missed that.
Can't golf it anymore.

  • 1
    \$\begingroup\$ You can get this down to 24 characters: x∊{1↓⍵,+/⍵}⍣{x≤⊃⍺}⍎¨⍕x←⎕. In the power function, is the "after" value. \$\endgroup\$
    – marinus
    Nov 18, 2013 at 17:41

Common Lisp, 134

CL can be quite unreadable at times.

(defun k(n)(do((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))((>=(car a)n)(and(> n 9)(=(car a)n)))))

Some formatting to avoid horizontal scrolling:

(defun k(n)
    ((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))
    ((>=(car a)n)(and(> n 9)(=(car a)n)))))


(loop for i from 10 to 1000
      if (k i)
      collect i)

=> (14 19 28 47 61 75 197 742)

F# - 184 chars

I hope it's ok that I'll participate in my own challenge.

let K n=
let rec l x=if n<10 then false else match Seq.sum x with|v when v=n->true|v when v<n->l(Seq.append(Seq.skip 1 x)[Seq.sum x])|_->false
string n|>Seq.map(fun c->int c-48)|>l

Edit Fixed a bug regarding small numbers.

  • \$\begingroup\$ It's perfectly fine :) \$\endgroup\$
    – beary605
    Dec 28, 2012 at 17:27
  • \$\begingroup\$ Your solution returns true for n<10 which I think should be false. \$\endgroup\$
    – Howard
    Dec 28, 2012 at 17:49
  • \$\begingroup\$ You are right. I should look into that. \$\endgroup\$ Dec 28, 2012 at 18:08

K, 55



14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935 93993

PowerShell: 120 128 123 111 110 97


$i=read-host takes input from the user, stores it in $i.

$j=(...)-split''|?{$_} breaks up the digits from $i into an array and stores it in $j.

Thanks to Rynant for pointing out that -ne'' is unnecessary.

While($x-lt$i) sets the following Fibonnaci-like loop to run until the sum variable, $x, reaches or exceeds $i.

$x=0 zeroes out $x, so it's ready to be used for summing (necessary for when the loop comes back around).

$j|%{$x+=$_} uses a ForEach-Object loop to add up the values from $j into $x.

$null,$j=$j+$x shifts the values in $j left, discarding the first, while appending $x.

Yay! I finally figured out a shorter way to do shift-and-append, and got this script under 100!

$x-eq$i after the while loop completes, tests if the sum value, $x, equals the initial value, $i - generally indicative of a Keith Number.

-and$x-gt9 invalidates single-digit numbers, zero, and negative numbers, which cannot be Keith Numbers.

This script is a bit "messy". It can gracefully handle $i and $j being leftover, but you'll need to clear $x between runs.

Thanks to Keith Hill and mjolinor for some methods of breaking numbers into digits which were used in earlier versions of this script. While they are not in the final version, they did provide for a great learning experience.

  • \$\begingroup\$ You can remove the -ne'' so that it is just ?{$_}. \$\endgroup\$
    – Rynant
    Nov 15, 2013 at 16:37
  • \$\begingroup\$ Thanks @Rynant. Looks like I can also trim it down one more by replacing $i=read-host;$j=$i-split''|?{$_}' with $j=($i=read-host)-split''|?{$_}. \$\endgroup\$
    – Iszi
    Nov 15, 2013 at 16:49

Husk, 11 bytes


Try it online!

Returns the iteration at which the Keith number is present, otherwise 0.

This challenge is perfect for Husk.


   ¡o       create an infinite list, starting with
          d the digits of the input
      ↑_L¹  take length(input) numbers from the end
     Σ      and sum to compute the next number
S£o         is the input present in the list?

Ruby, 82

def keith?(x)
  l="#{x}".chars.map &:to_i
  0while(l<<(s=l.inject :+)).shift&&s<x

Suspect Python's a better tool for this one.


C, 123

    int g[9],i,n,s,t=v;
    return n>1&&s==v;

test via harness:

        if(k(i)) printf("%d ",i);


14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909
  • \$\begingroup\$ You can replace i=(i+n-1)%n;t=g[i];g[i]=s;s=s*2-t; with i+=n-1;t=g[i%n];g[i%n]=s;s+=s-t; and save two chars. \$\endgroup\$
    – schnaader
    Dec 30, 2012 at 0:51

R, 116

Python rip-off:

a=scan();n=as.numeric(strsplit(as.character(a),"")[[1]]);while(a>n[1])n=c(n[-1],sum(n));if((n[1]==a)&&(a>9))T else F

Perl, 90

sub k{$-=shift;$==@$=split//,$-;push@$,eval join'+',@$[-$=..-1]while@$[-1]<$-;grep/$-/,@$}

A fun exercise! I know it's an old post but I noticed perl was missing!

I'm sure I can improve the way I build this from digesting the other responses more thoroughly, so I'll likely revisit this!


Smalltalk - 136 char

 [:n|s:=n asString collect:[:c|c digitValue]as:OrderedCollection.w:=s size.[n>s last]whileTrue:[s add:(s last:w)sum].^(s last=n and:n>9)]

Send this block value:


Python3 104

def k(z):
 while b<z:a=a[1:]+[b];b=sum(a)
#END_CODE score: 104

print([i for i in filter(k, range(1,101))])  #[14, 19, 28, 47, 61, 75]

And it is a function ;)


Python - 116 chars

Not really an expert at codegolf, so there you have it- my first try.

x=input();n=`x`;d=[int(i)for i in n];f=d[-1]
while f<x:d+=[sum(d[-len(n):])];f=d[-1]
if f==x>13:print 1
else:print 0

Make 2 changes for a function:

  • Change print to return
  • Assign x to be the parameter

P.S. I second @beary605- add a built-in to separate the digits/characters/whatever.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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