14
\$\begingroup\$

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

\$\endgroup\$
  • \$\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 '13 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\$ – Smetad Anarkist Nov 15 '13 at 8:49
  • \$\begingroup\$ Does it have to output true / false or can it be anything truthy/falsey? \$\endgroup\$ – Cyoce Oct 10 '16 at 0:49

17 Answers 17

7
\$\begingroup\$

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.

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

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ @PeterTaylor Look at the link provided where I did exactly that - and it works... \$\endgroup\$ – Howard Dec 29 '12 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 '12 at 19:20
  • \$\begingroup\$ I must have not refreshed, because my comment is applicable to version 1. \$\endgroup\$ – Peter Taylor Dec 29 '12 at 20:14
4
\$\begingroup\$

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.

\$\endgroup\$
  • 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 '13 at 17:41
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can remove the -ne'' so that it is just ?{$_}. \$\endgroup\$ – Rynant Nov 15 '13 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 '13 at 16:49
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\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 '12 at 0:51
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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:

\$\endgroup\$
0
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to CodeGolf.SE! Since this question is code-golf, you should golf your code (remove whitespaces, new lines...) \$\endgroup\$ – Vereos Mar 25 '14 at 8:05
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Ruby (with OOP)

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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