4
\$\begingroup\$

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])
\$\endgroup\$
5
  • \$\begingroup\$ Heads up: the numbers overflow 32-bit int. You'll need big integers (or at least 64-bit integers) for the final rows. \$\endgroup\$
    – Joey Adams
    Jul 29 '11 at 4:51
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 29 '11 at 6:45
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Jul 29 '11 at 14:15
  • \$\begingroup\$ @Peter Taylor: Sounds good. Now all you have to do is code-golf the proof ;) \$\endgroup\$
    – Briguy37
    Jul 29 '11 at 18:29
  • \$\begingroup\$ @Peter Taylor: I dare you to write the proof in Coq or similar. \$\endgroup\$
    – Joey Adams
    Jul 29 '11 at 19:32

12 Answers 12

7
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 29 '11 at 23:30
  • \$\begingroup\$ 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++ \$\endgroup\$ Aug 2 '11 at 20:41
  • \$\begingroup\$ @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! \$\endgroup\$
    – Briguy37
    Aug 3 '11 at 13:52
  • \$\begingroup\$ 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 \$\endgroup\$
    – shesek
    Aug 18 '11 at 0:49
  • \$\begingroup\$ @shesek: Updated, thanks much! \$\endgroup\$
    – Briguy37
    Sep 1 '11 at 13:28
7
\$\begingroup\$

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

Mathematica 82 chars

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

-> 17
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Nice one. I borrowed some of your ideas, and found a few places to save a few characters. \$\endgroup\$
    – recursive
    Aug 18 '11 at 14:39
3
\$\begingroup\$

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

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

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
\$\endgroup\$
1
  • \$\begingroup\$ until[]==l instead of while !l.empty? saves 5 characters \$\endgroup\$
    – Howard
    Jul 29 '11 at 6:40
1
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ I don't think you need the =1 in c=1 in the golfed version? \$\endgroup\$ Jul 29 '11 at 16:07
  • \$\begingroup\$ You were right thanks, well spotted. \$\endgroup\$ Jul 29 '11 at 16:27
  • 1
    \$\begingroup\$ The i loop can be shortened by counting down. for(i=e;i--;c+=a) (i think) \$\endgroup\$
    – st0le
    Aug 1 '11 at 10:01
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 1 '11 at 21:38
  • \$\begingroup\$ Can't you just use int if you change the %67 to %=67? \$\endgroup\$ Aug 1 '11 at 22:03
1
\$\begingroup\$

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.

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

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.

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

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

GolfScript, 39 38 characters

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