# [Easy] Find 9

Michael Morris

Ranch Hand

Posts: 3451

posted 13 years ago

Excluding 1-9, find the smallest consecutive group of 9 positive integers such that the first ends in 1 and the last ends in 9 and the result of dividing each by its last digit yields no remainder. For example:

512/2 has no remainder.

123/3 has no remainder.

637/7 has no remainder.

512/2 has no remainder.

123/3 has no remainder.

637/7 has no remainder.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Eric Pascarello

author

Rancher

Rancher

Posts: 15385

6

posted 13 years ago

Wrote this in < minute....lol

http://www10.brinkster.com/A1ien51/game/Solver9.htm

I was expecting the number to be in the 1000 range, but was surprised to see it was higher.

Eric

http://www10.brinkster.com/A1ien51/game/Solver9.htm

I was expecting the number to be in the 1000 range, but was surprised to see it was higher.

Eric

Michael Morris

Ranch Hand

Posts: 3451

Eric Pascarello

author

Rancher

Rancher

Posts: 15385

6

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 13 years ago

That's about how long it takes in a real programming language too. Except we don't have to wait several more seconds afterwards for the result.

There are probably ways to reduce the number of computations more (aside from eliminating checks for 1, 2, 5, which are trivial) but given how quickly the answer is found anyway, it hardly seems necessary.

[ June 01, 2003: Message edited by: Jim Yingst ]

**Wrote this in < minute....lol**

That's about how long it takes in a real programming language too. Except we don't have to wait several more seconds afterwards for the result.

There are probably ways to reduce the number of computations more (aside from eliminating checks for 1, 2, 5, which are trivial) but given how quickly the answer is found anyway, it hardly seems necessary.

[ June 01, 2003: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

posted 13 years ago

Mine's a bit different than Jim's:

[ June 01, 2003: Message edited by: Jessica Sant ]

[ June 01, 2003: Message edited by: Jessica Sant ]

- Jess

Blog:KnitClimbJava | Twitter: jsant | Ravelry: wingedsheep

Eric Pascarello

author

Rancher

Rancher

Posts: 15385

6

Michael Morris

Ranch Hand

Posts: 3451

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 13 years ago

For the record, mine was just intended as a quick and dirty solution; once I saw how quickly the solution popped up, any further refactoring seemed pointless. Though looking at other solution, I did like Michael's use of i > 0 to terminate the loop in case no solution was found otherwise. I had started to put in i <= (Integer.MAX_VALUE) - 10) but first I decided to run the program anyway; turned out it didn't matter. But using i > 0 is an elegant check I'll remember next time.

"I'm not back." - Bill Harding, *Twister*

Roy Tock

Ranch Hand

Posts: 83

posted 13 years ago

Mathematical solution:

This problem is equivalent to finding the smallest positive integer (divisible by 10) that is (also) divisible by 2, 3, 4, 5, 6, 7, 8, and 9. Since the number is divisible by 2 and 5, it's trivially divisible by 10.

To find the LCM of a series of numbers, find their prime representations, choose the max exponent of each prime factor, and multiply together.

9 = 3^2

8 = 2^3

7 = 7

6 = 2 * 3

5 = 5

4 = 2^2

3 = 3

2 = 2

The LCM is 7 * 5 * 3^2 * 2^3, or 2520, so the nine integers we seek are the nine following 2520.

This problem is equivalent to finding the smallest positive integer (divisible by 10) that is (also) divisible by 2, 3, 4, 5, 6, 7, 8, and 9. Since the number is divisible by 2 and 5, it's trivially divisible by 10.

To find the LCM of a series of numbers, find their prime representations, choose the max exponent of each prime factor, and multiply together.

9 = 3^2

8 = 2^3

7 = 7

6 = 2 * 3

5 = 5

4 = 2^2

3 = 3

2 = 2

The LCM is 7 * 5 * 3^2 * 2^3, or 2520, so the nine integers we seek are the nine following 2520.