**From New Scientist #1374, 8th September 1983** [link]

At the car factory where I work the latest model is pouring off the assembly line. Their chassis numbers started at 1 and they have been numbered consecutively since.

In the quality control department we have to check some of the cars. The first one we checked was one of the early ones off the line. Then we checked all cars whose chassis numbers were multiples of the first number which we had checked.

Unfortunately this system let too many mistakes go undetected and so the manager asked us to check an extra car last week. He also introduced new rules by which we would subsequently have to check all cars whose chassis numbers were the sum of two numbers (possibly the same) which we had already checked.

Car number 77777 has just gone through unchecked and we are now checking number 77778. Our union is demanding extra staff in this department because we now realise that under the new rules we are going to have to check *every* car from now on.

How many of the first 77777 cars were checked?

**Note:** I am still waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment. The latest estimate is that I’ll have a connection by the end of October 2014.

[enigma228]

### Like this:

Like Loading...

We can get an analytical solution to this puzzle using

Frobenius Numbers[ http://en.wikipedia.org/wiki/Frobenius_number ].For integers

a,bwithgcd(a, b) = 1, theFrobenius Number:is the largest integer not expressible as

i.a + j.b(fori,jnon-negative integers).We require

F(a, b) = n, wheren= 77777.So:

Also the number of non-expressible integers is:

Substituting for

b, we get:which is independent of

aandb.The non-expressible integers correspond to the cars that were not checked. So the number of cars checked is:

and as

n= 77777, the number of cars checked is 38888.This Python program uses the formulae given above to determine the possible numbers of the two exemplar cars,

aandb. It runs in 30ms.Solution:38,888 of the first 77,777 cars were checked.It finds 9 possible pairs of numbers:

As expected, each pair gives rise to the same solution – that 38,888 of the first 77,777 cars were checked.

Given that

ais “one of the early cars off the line”, andbcame off the line “last week” and they are now checking car 77777 it seems that the most likely candidates are (a,b) = (3, 38890) or (4, 25927).Either way they are producing thousands of cars a day, so the car can only have been in production for a couple of weeks.

Here’s a program that finds the same pairs as given above, but constructively, so it’s a lot slower. It runs in 28m16s.