Test if given number if 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

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 6

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 7

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 8

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 9

Adding Ruby OOPs

class Recreationalmathematics
def Check_KeithSequence(digit) 
    sequence,sum=digit.to_s.split(//).to_a,0
    while(sum<digit) do
        sum=0
        sequence.last(digit.to_s.size).each{|v|  sum=sum+v.to_i}
        sequence<<sum
    end 
    return (sum==digit)?"true":"false" 
end
end
test = Recreationalmathematics.new
puts test.Check_KeithSequence(197)
puts test.Check_KeithSequence(198)

Answer 10

Haskell (137)

k m|length(show m)>1=o[Data.Char.ord c-48|c<-show m]m|1>0=1<1where o n s|v==s=1>0|v>s=1>1|1>0=o r s where v=y n;r=tail n++[v];y=foldl(+)0

Output:

Prelude> :l keith.hs
*Main> [x | x <-[1..10000], k x]
[14,19,28,47,61,75,197,742,1104,1537,2208,2580,3684,4788,7385,7647,7909]

Answer 11

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