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

## 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
``````
-
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
``````
-
Nice! :) ........ – st0le Aug 19 '11 at 3:47

# 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
Thanks @Howard! :) – st0le Jul 29 '11 at 9:26

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

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