Posts Tagged ‘cmd’

Triangle numbers

June 17, 2009

I feel bad for not having worked on any problems since Problem 6. So here is my Mathematica solution to Problem 12.

Triangle[n_] := n (n + 1)/2;
n = 1;
While[Length[Divisors[Triangle[n]]] < 500, n++]; Print[Triangle[n]] [/sourcecode] As usual, I cheated by not programming in Python or Sage. But I figure this is better than nothing. I suspect I would get a lot more out of this programming project if I thought about how to write my own Divisors algorithm. Oh well.

Advertisements

Followup to BiggestPalindrome

May 23, 2009

I found a way to shave my running time down from 5.75 seconds to about 0.1 seconds. Basically, I just eliminated a lot of unnecessary multiplications and palindrome checks.


NotPalindrome[x_] := (y = ToString[x]; y != StringReverse[y]);

BiggestPalindrome[n_] :=
 (x = 1;
 For[i = 10^n - 1, i > 10^(n - 1) - 1, --i,
 For[j = i; m = i*j, j > 10^(n - 1) - 1 && NotPalindrome[m] && m >= x, --j, m = i*j];
 If[m >= x, x = m]];
 x)

It takes about 0.21 seconds to compute the largest palindrome that is the product of two four digit numbers, and about 19.5 seconds to compute the largest palindrome that is the product of two five digit numbers.

BiggestPalindrome

May 22, 2009

Once again, I cheated by using Mathematica instead of one of the two sanctioned computing environments (Python or Sage). To test whether or not a number was a palindrome, I used Mathematica’s built-in abilities to convert an expression into a string, and to reverse the characters in any given string. Here is my code (it is based on an algorithm I remember Eric describing last week):

Palindrome[x_] := (y = ToString[x]; y == StringReverse[y]);

BiggestPalindrome[n_] := (x = 1;
  For[i = 10^n - 1, i > 10^(n - 1) - 1, --i,
   For[j = i, j > 10^(n - 1) - 1, --j, m = i*j;
    If[Palindrome[m] && m >= x, x = m]]]; x)

Typing BiggestPalindrome[n] will give the largest palindrome that is the product of two n-digit numbers.It took Mathematica about 5.75 seconds to compute the solution when n=3. I asked Mathematica to give me the answer for n=4, but I got tired of waiting for it to finish.

I’m sure there must be a way to cut down on the number of loops to go through. If there is, I’m sure somebody else will produce it.

n(n+1)/2

May 15, 2009

My new approach to Problem 1 is different from Eric’s. We all know the formula

1+2+3+\cdots+n = \dfrac{n(n+1)}{2}.

We can use this formula to very quickly add the multiples of 3 between 1 and 999, namely, add all the integers between 1 and 333, and then multiply by 3. Similarly, we can add the integers between 1 and 195 and then multiply by 5 to get the sum of all multiples of 5 between 1 and 999. Putting those together, we’ve double-counted the multiples of 15, so we subtract the multiples of 15 to get the sum of all multiples of 3 or 5 between 1 and 999.

In general, if you had more divisors, you’d have to use some sort of alternating sum/inclusion-exclusion principle argument to get rid of the stuff you double/triple/quadruple/etc.-counted.

a=3
b=5
c=999
d=a*b
e=c//a
f=c//b
g=c//d
a*e*(e+1)/2+b*f*(f+1)/2-d*g*(g+1)/2

I did not write code to handle more divisors. I suppose you could just stick my equation into Eric’s code, and that would work.

Mathematica

May 14, 2009

I tried the problem first in Mathematica, and then in Sage. Here is my Mathematica code:

j = 0;
For[i = 1, i < 1000, i++, j += If[Divisible[i, 3], i, If[Divisible[i, 5], i, 0]]]; j [/sourcecode] Mathematica claims a running time of 0.005759 seconds. Now here is the code I ran in Sage: [sourcecode language='python'] j=0; def is_divisible_by(number,divisor): return number%divisor == 0 for i in range(1,1000): if is_divisible_by(i,3): j+=i if is_divisible_by(i,3)==false: if is_divisible_by(i,5): j+=i print(j) [/sourcecode] Sage tells me that it took 0.02s to run that code. Then I saw some of your previouly posted solutions, and amended my code so that the for loop looked like [sourcecode language='python'] for i in range(1,1000): if is_divisible_by(i,3) or is_divisible_by(i,5): j+=i [/sourcecode] (i.e., I made my code almost exactly the same as some of the previously posted solutions). Now Sage says it takes 0.01s to compute the answer.