# Multiples of 67 in a constructed array of arrays?

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

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

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

• 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
• 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
• @shesek: Updated, thanks much! – Briguy37 Sep 1 '11 at 13:28

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,nmod67<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  • replace ==0 by <1 – st0le Jul 29 '11 at 9:27 • You can replace f with tail>>=zipWith(+) – proud haskeller Oct 11 '14 at 18:54 • You can also change the inners of the comprehention to n<-(take50$iterate f[1,3..99])>>=id,  – proud haskeller Oct 11 '14 at 18:57
• Nice trick with using sum – proud haskeller Oct 11 '14 at 18:57

## Mathematica 82 chars

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

-> 17


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

• 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

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


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

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

• until[]==l instead of while !l.empty? saves 5 characters – Howard Jul 29 '11 at 6:40

# C++ 133131 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>

int main(){
curr=start;
for(int i=1;i<=end_line;++i){
if(curr%67){
}else{
ret++;
}
}
}
std::cout<<ret;
}

• 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. – Scott Logan Jul 29 '11 at 16:27
• 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. – Scott Logan 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

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

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

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


### GolfScript, 39 38 characters

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