Multiples of 67 in a constructed array of arrays?

Question

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

Answer 1

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.

Answer 2

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

Answer 3

Mathematica 82 chars

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

-> 17

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

GolfScript, 39 38 characters

100,{2%},0\{.{67%!},,@+\(\{.@+}%\;.}do