Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
    
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? –  Iszi Nov 14 '13 at 19:55
    
Depending on your solution single digit numbers could show up as true. So you should check for potential errors in input. –  Smetad Anarkist Nov 15 '13 at 8:49
add comment

17 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Nice idea with the 0>. Unfortunately I can +1 only once. –  Howard Dec 30 '12 at 8:00
add comment

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.

share|improve this answer
    
You may save two chars if you compare with n[0] instead of n[-1]. –  Howard Dec 28 '12 at 18:10
    
Save five more with print 9<a==n[0]. –  r.e.s. Nov 14 '13 at 3:32
add comment

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.

share|improve this answer
    
@PeterTaylor Look at the link provided where I did exactly that - and it works... –  Howard Dec 29 '12 at 19:12
    
@PeterTaylor Looking at your solution I even could reduce the number of chars further in my approach. –  Howard Dec 29 '12 at 19:20
    
I must have not refreshed, because my comment is applicable to version 1. –  Peter Taylor Dec 29 '12 at 20:14
add comment

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.

share|improve this answer
    
You can get this down to 24 characters: x∊{1↓⍵,+/⍵}⍣{x≤⊃⍺}⍎¨⍕x←⎕. In the power function, is the "after" value. –  marinus Nov 18 '13 at 17:41
add comment

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)
share|improve this answer
add comment

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.

share|improve this answer
    
It's perfectly fine :) –  beary605 Dec 28 '12 at 17:27
    
Your solution returns true for n<10 which I think should be false. –  Howard Dec 28 '12 at 17:49
    
You are right. I should look into that. –  Smetad Anarkist Dec 28 '12 at 18:08
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
    
You can remove the -ne'' so that it is just ?{$_}. –  Rynant Nov 15 '13 at 16:37
    
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''|?{$_}. –  Iszi Nov 15 '13 at 16:49
add comment

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.

share|improve this answer
add comment

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
share|improve this answer
    
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. –  schnaader Dec 30 '12 at 0:51
add comment

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)
share|improve this answer
add comment

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
share|improve this answer
add comment

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!

share|improve this answer
add comment

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:

share|improve this answer
add comment

Java - 1437

import java.io.*;
class keith
{
    public int reverse(int n)
    {
        int i,c=0;
        while(n>0)
        {
            c=(c*10)+(n%10);
            n/=10;
        }
        return(c);
    }
    public int countdigit(int n)
    {
        int i,c=0;
        while(n>0)
        {
            c++;
            n/=10;
        }
        return(c);
    }
    public void keith_chk()throws IOException
    {
        BufferedReader br=new BufferedReader(
        new InputStreamReader(System.in));
        int n,digi,r,p=0,a,tot=0,i;
        System.out.print("Enter number :-");
        n=Integer.parseInt(br.readLine());
        digi=countdigit(n);

        int ar[]=new int[digi+1];
        r=reverse(n);
        while(r>0)
        {
            a=r%10;
            ar[p++]=a;
            tot=tot+a;
            r/=10;
        }
        ar[p]=tot;
        while(true)
        {
            for(i=0;i<=p;i++)
            System.out.print(ar[i]+"\t");
            System.out.println(); 
            if(tot == n)
            {
                System.out.print("Keith Number....");
                break;
            }
            else if(tot > n)
            {
                System.out.print("Not Keith Number.....");
                break;
            }
            tot=0;
            for(i=1;i<=p;i++)
            {
                ar[i-1]=ar[i];
                tot=tot+ar[i];
            }
            ar[p]=tot;
        }
    }
}
share|improve this answer
3  
Welcome to CodeGolf.SE! Since this question is code-golf, you should golf your code (remove whitespaces, new lines...) –  Vereos Mar 25 at 8:05
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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