The Final POTW

890

890 is correct.

The key is to notice that if n is a multiple of 10, then n^3 + 100 will be a multiple of 100. So we look for other numbers, relatively prime to 100, that can be additional divisors. We notice that for any m such that m mod 9 = 8, it will also be true that m^3 mod 9 = 8, and 100 mod 9 = 1. So we try 890, and find that 890^3 + 100 = 704969100. The digits in that number sum to 27, which is a multiple of 9, and since it ends with two zeroes, it must also be a multiple of 100. Therefore 890^3 + 100 is indeed divisible by 890 + 10, and to verify we find that 704969100 / 900 = 783299.

If we look for other numbers of the form 100m -10, we find that 890 is the largest that satisfies (100m - 10) mod m = m - 1. So it is the desired solution.

I haven't tried all of the possibilities, so there may be some I have overlooked, but among the smaller positive integers that work are 2, 5, 10, 15, 40, 90, and 290. The first two I found by trial and error; the others I found by a similar method to the above.

I guess I'm confused. Should the problem be worded as, "...evenly divisible..."?

Not being a math guy, I wrote a Windows PowerShell script to run through some possibilities:

$array = (1..100)
foreach ($n in $array) {
$ncubed = [math]::pow($n,3)
$ncubedplus = $ncubed + 100
$finaln = $ncubedplus / ($n + 10)
"$n ==> $finaln"
}

Every number can be divided by some other number, but only a handful divide evenly. If that's the actual intent, then some modulo step would be needed to find just the whole integers.

@James: It's usually implicit when the problem specifies that you are dealing with integers that "divisible" means evenly divisible.

A C code fragment to do this by brute force (all variables are of type long):
for(i = 1; i < 1000; i++){
icubeplus = i * i * i + 100;
iplus = i + 10;
if(icubeplus mod iplus == 0)
printf("%6d %14d %6d %10d\n",i,icubeplus,iplus,icubeplus/iplus);
}

The script you posted won't find the answer, because as noted above, there are at least two numbers greater than 100 that satisfy the condition (namely, 290 and 890).

Did I oversimplify this one? z^3 + 100= (z^3 + 1000) - 990. The z^3 + 1000 term is divisible by z+10 for any z. Thus the whole ecpression is divisible by z+10 iff 900 is. The largest integer divisible by 900 is of course 900. z+10=900 giving z=890 as the solution.

James, the theme of this semester's POTW is number theory. In number theory, the notion of "divisible" is very precisely defined. An integer a is divisible by another integer b if and only if an integer c exists such that a=bc. That definition precludes any cases where the quotient of the integers is not an integer. For example, 10 is divisible by 2, but not by 4 because 2x5 = 10, but no integer value for c exists such that 4c=10, only the noninteger value 5/2. It is worth noting that an integer is always divisible by itself since for any a there is an integer value for c such that a = ac, namely c=1. I made use of this fact in my POTW solution above.

Eric, referring to my solution, 440 will also be a solution. Any value of x such that 900 is divisible by x+10 will work. Factors of 900 are 2,3,5,6,9,10,12,15,18,20,25,30,36,45,50,60,75,90,100,150,180,300,450 and 900. The list of all solutions is thus -8,-7,-5,-4,-1,0,2,5,8,10,15,20,26,35,40,50,65,80,90,140,170,290,440, and 890.

Eric Lund, thanks for the reply. You're correct that my code would not have found the answer, in that I set my array too small, from 1 to 100. Playing with it more, I set the array higher, and quickly found that 890 was the maximum value.

My code would be modifed as such to find only whole integers:

$array = (1..1000000)
foreach ($n in $array) {
$ncubed = [math]::pow($n,3)
$ncubedplus = $ncubed + 100
$finaln = $ncubedplus / ($n + 10)
if ($finaln % 1 -eq 0) {
“$n ==> $finaln”
}
}

19 solutions to the problem, with 890 being the largest.

I went the other way around, by subbing m=n+10 and recasting the problem as the greatest m such that (m-10)^3 + 100 is divisible by m. The constant term in expanding the cube is -1000, to which 100 is added to get -900. This means that in order for m to divide (m-10)^3 + 100 evenly, it must be a factor of 900, the greatest being 900. Subbing back, n=900-10=890