Test if given number is a Keith number

Question

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.

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

Input

An integer.

Output

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

Answer 1

GolfScript (31 25 chars)

..[10base{.{+}*+(\}@*]?0>

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.

Answer 2

Python (78 75)

a=input()
n=map(int,`a`)
while a>n[0]:n=n[1:]+[sum(n)]
print(a==n[0])&(a>9)

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.

Answer 3

GolfScript, 32 29 characters

...[10base\{.{+}*+(\}*]&,\9>&

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.

Answer 4

APL, 36 34 39 36 33 29 27

*+/x={(∇⍣(⊃x>¯1↑⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

Output 1 if Keith, 0 otherwise

GolfScript strikes again!!

---

Edit

+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

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

Explanation

⍎¨⍕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.

---

Edit

1=+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

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

---

Yet another edit

+/x=¯1↓{(∇⍣(x>⊢/⍵))1↓⍵,+/⍵}⍎¨⍕x←⎕

Explanation

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

+/x=1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

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

x∊1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

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

Answer 5

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

Test:

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

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

Answer 6

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.

Answer 7

K, 55

{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}

.

k)&{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}'!100000
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935 93993

Answer 8

PowerShell: 120 128 123 111 110 97

$j=($i=read-host)-split''|?{$_};While($x-lt$i){$x=0;$j|%{$x+=$_};$null,$j=$j+$x}$x-eq$i-and$x-gt9

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

Answer 9

Husk, 11 bytes

S£o¡oΣ↑_L¹d

Try it online!

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

This challenge is perfect for Husk.

Explanation

S£o¡oΣ↑_L¹d
   ¡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?

Answer 10

Ruby, 82

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

Suspect Python's a better tool for this one.

Answer 11

C, 123

k(v){
    int g[9],i,n,s,t=v;
    for(n=s=0;t;t/=10)s+=g[n++]=t%10;
    for(i=n;s<v;){
        i=(i+n-1)%n;
        t=g[i];g[i]=s;s=s*2-t;
    }
    return n>1&&s==v;
}

test via harness:

main(i){
    for(i=0;i<20000;i++)
        if(k(i)) printf("%d ",i);
}

gives:

14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909

Answer 12

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

Answer 13

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!

Answer 14

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:

Answer 15

Python3 104

#BEGIN_CODE
def k(z):
 c=str(z);a=list(map(int,c));b=sum(a)
 while b<z:a=a[1:]+[b];b=sum(a)
 return(b==z)&(len(c)>1)
#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 ;)

Answer 16

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.