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.

A triangle-shaped table is constructed such the first row is "1, 3, 5, 7, ..., 99"

Each subsequent row has the following properties:

  • One less element than the row above
  • Each element is the sum of the two elements above it

Like so:

1   3   5    7    9    11 ....
  4   8   12   16   20 ....
    ...............

This continues until the last row with one element.

How many elements are divisible by 67?

Fewest lines, chars, or whatever may win. Depends on ingenuity.

EDIT: the answer is 17 but you have to prove it.

ADDENDUM: I have three-line python code for this but try to beat it:

a = [[2*i+1 for i in range(50)]]
while len(a[-1])>1:a.append([a[-1][i]+a[-1][i+1] for i in range(len(a[-1])-1)])
print len([i for b in a for i in b if i%67==0])
share|improve this question
    
Heads up: the numbers overflow 32-bit int. You'll need big integers (or at least 64-bit integers) for the final rows. –  Joey Adams Jul 29 '11 at 4:51
    
Is this the way to go? Inform the others of possible pitfalls? I would prefer to wait for the first users, trapping into the trap. –  user unknown Jul 29 '11 at 6:45
3  
By induction, row (2n) = 4^n (2n+1, 2n+3, ..., 99-2n); and row (2n+1) = 4^(n+1) (n+1, n+2, ..., 49-n). gcd(4, 67) = 1, 49 < 67 < 99 < 2*67, so there is one number divisible by 67 in the even rows until row 32 (=99-67), for a total of 17. If I put this in a comment then I can justify hard-coding the answer, and when I golf I remove comments. Therefore I've downvoted this as a bad question. –  Peter Taylor Jul 29 '11 at 14:15
    
@Peter Taylor: Sounds good. Now all you have to do is code-golf the proof ;) –  Briguy37 Jul 29 '11 at 18:29
    
@Peter Taylor: I dare you to write the proof in Coq or similar. –  Joey Adams Jul 29 '11 at 19:32
add comment

12 Answers 12

up vote 7 down vote accepted

JavaScript: 91, 88 (thanks trinithis), 84, 77 (thanks again trinithis), 75 (thanks shesek), 74 Characters (thanks Shmiddty)

91-->88 - See Trinithis's comment
88-->84 - moved j-- into conditional check.
84-->77 - See trinithis's comment (removed {} from for loops, ignored first index of a array) plus some additional work (fixed logic for building arrays and incrementing counters)
77-->75 - See Shesek's comment (instead of (condition)&&val++: val+=(condition))
75-->74 - See Shmiddty's comment (instead of i=c=1,a=[]: a=[i=c=1])

Golfed:

for(a=[i=c=1];i<51;)for(a[i]=i*2-1,j=i++;j>1;)c+=1>(a[--j]=a[1+j]+a[j])%67

Ungolfed:

/**
 * i - counter for array index and array initialization
 * c - count of elements divisible by 67
 * a - array of numbers in diagonal bottom-to-right row. 
 *        For example, here are the first 3 iterations:  [1], [4,3], [12,8,5]
 * j - index into array a
 */
for(a=[i=c=1];i<51;){
    a[i]=i*2-1;
    for(j=i++;j>1;){
        c+=1>(a[--j]=a[1+j]+a[j])%67
    }
}

Here's a fiddle for both as well as a test that outputs what is in the arrays for the first 3 iterations.

Note: I initialize the count to 1 because the first row [1,3,5..67..97,99] has one number divisible by 67. That way, I did not have to worry about checking the first row.

share|improve this answer
    
if(0==(a[j]=a[j]+a[j+1])%67)c++ -> 1>(a[j]=a[j]+a[j+1])%67&&c++ Might be able to use ! instead of 0== or 1> if you can figure it out. –  Thomas Eding Jul 29 '11 at 23:30
    
@trinithis Thanks much! –  Briguy37 Aug 1 '11 at 13:38
    
73 chars: for(i=c=1,a=[];i<51;)for(a[i]=i*2-1,j=i++;j;)1>(a[--j]=a[j]+a[j])%67&&c++ –  Thomas Eding Aug 2 '11 at 20:41
    
@trinithis: Thanks! One thing: I didn't understand a[--j]=a[j]+a[j] in your code. Because of this, I did some debugging and ended up finding a mistake with my second iteration (a[j]=a[j--]+a[j] is not equal to a[j-1]=a[j]+a[j-1] but instead a[j]=a[j]+a[j-1]). This is fixed in the above version, and is much shorter because of you, so thanks again for the help! –  Briguy37 Aug 3 '11 at 13:52
    
Sliced down 2 more characters by adding the boolean result of 1>... to c (which is casted to an integer), for(i=c=1,a=[];i<51;)for(a[i]=i*2-1,j=i++;j>1;)c+=1>(a[--j]=a[1+j]+a[j])%67 –  shesek Aug 18 '11 at 0:49
show 3 more comments

Haskell - 86 chars

98 → 92: Use list comprehensions and sum instead of filter and length.

92 → 86: Convert nested list comprehensions into one, and change ==0 to <1 (thanks st0le).

f s=zipWith(+)s$tail s
main=print$sum[1|r<-take 50$iterate f[1,3..99],n<-r,n`mod`67<1]

Ungolfed:

initialRow :: [Integer]
initialRow = [1,3..99]

nextRow :: (Num a) => [a] -> [a]
nextRow xs = zipWith (+) xs (tail xs)

triangle :: [[Integer]]
triangle = takeWhile (not . null) $ iterate nextRow initialRow

main = print $ length $ filter ((== 0) . (`mod` 67)) $ concat triangle
share|improve this answer
    
replace ==0 by <1 –  st0le Jul 29 '11 at 9:27
add comment

Mathematica 82 chars

Count[Mod[#,67]==0&/@Flatten@NestList[2MovingAverage[#,2]&,Range[1,99,2],49],True]

-> 17
share|improve this answer
add comment

Python 95 bytes

l,c=range(1,100,2),0
while l:c+=len([i for i in l if i%67<1]);l=map(sum,zip(l,l[1:]))
print c
share|improve this answer
    
Nice one. I borrowed some of your ideas, and found a few places to save a few characters. –  recursive Aug 18 '11 at 14:39
add comment

Python

85 bytes - thanks to st0le

l,c=range(1,100,2),0
while l:c+=sum(i%67<1for i in l);l=map(sum,zip(l,l[1:]))
print c
share|improve this answer
    
Nice! :) ........ –  st0le Aug 19 '11 at 3:47
add comment

J, 48

1225-~+/,-.*67|((<:/|.)a)*(+1&|.)^:a>:2*a=:i.50x

Explanation (bits of it, anyway):

  • a is 0 .. 49
  • >:2*a is 1 3 5 ...
  • The verb (+1&|.) shifts a row and adds it to the original to get the desired next row (plus extras, since the result is still 50 elements).
  • (+1&|.)^:a>:2*a gives 50 rows of results. Row one is 1 3 5 etc, row 2 is 4 8 12 etc.
  • ((<:/|.)a) is a 50x50 matrix of 1 1 ... 1 1, 1 1 ... 1 0 etc. down to 1 0 ... 0 0. This zeroes out the 1225 extras. (1225 is the 49th triangular number.)
  • After taking mod 67 and counting, we subtract those 1225 zeroes that we know will be present.
share|improve this answer
add comment

Ruby 113 bytes

l,c=(1..100).step(2).to_a,0
[c+=l.count{|i|i%67<1},l=l.zip(l[1..-1]).map{|x,y|x+y if y}.compact!]until[]==l
p c
share|improve this answer
    
until[]==l instead of while !l.empty? saves 5 characters –  Howard Jul 29 '11 at 6:40
    
Thanks @Howard! :) –  st0le Jul 29 '11 at 9:26
add comment

C++ 133 131 125 chars, 2 Lines

#include<iostream>
__int64 c=1,s=1,r,a=2,e=51,i;int main(){for(;e;c=s+=s+a,a*=2)for(i=e--;--i;c+=a)c%67?0:r++;std::cout<<r;}

I'm not sure how portable this is with the use of __int64, if it does complains you can change it to long long.

Ungolfed

#include<iostream>

__int64 curr,start=1,ret,add=2,end_line=50;
int main(){
    for(;end_line>0;end_line--,add*=2){
        curr=start;
        for(int i=1;i<=end_line;++i){
            if(curr%67){
            }else{
                ret++;
            }
            curr+=add;
        }
        start+=start+add;
    }
    std::cout<<ret;
}
share|improve this answer
1  
I don't think you need the =1 in c=1 in the golfed version? –  Matthew Read Jul 29 '11 at 16:07
    
You were right thanks, well spotted. –  Bunnit Jul 29 '11 at 16:27
1  
The i loop can be shortened by counting down. for(i=e;i--;c+=a) (i think) –  st0le Aug 1 '11 at 10:01
    
@st0le, Thanks, rejigged it a bit as well though I'm now unsure about that c=1. I get the correct result without it but looking through the debug I don't think it is doing it the correct way, anyway i put it back in. –  Bunnit Aug 1 '11 at 21:38
    
Can't you just use int if you change the %67 to %=67? –  Peter Taylor Aug 1 '11 at 22:03
show 1 more comment

Q, 53 43

sum 0=(raze{1_msum[2]x}\[1+2*(!)50])mod 67

.

q)sum 0=(raze{1_msum[2]x}\[1+2*(!)50])mod 67
17i

Don't have to cast to long in q 3.0 which saved some characters.

share|improve this answer
add comment

scala, 125 chars:

def s(v:Seq[Long]):Seq[Long]=if(v.size==1)v else 
v++s(v.sliding(2).map(v=>v(0)+v(1)).toSeq)
s(1L to 99 by 2).count(_%67==0)

Since the first row contains the number 67, which is divisible by 67, and the next number, divisible by 67 is 2*67 is bigger than 99, we know that we start with count = 1.

share|improve this answer
add comment

Perl (84+1)

there might still be a way to shorten this :)

@q=grep$_%2,1..99;while(@q){$_%67or$c++for@q;$q[$_]+=$q[$_+1]for 0..$#q;pop@q}say$c
share|improve this answer
add comment

GolfScript, 39 38 characters

100,{2%},0\{.{67%!},,@+\(\{.@+}%\;.}do
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.