[seqfan] Re: Observation on the divisors of 136

[David Wilson]

Lemma 1:

If n >= 1 is odd, and divisible by all of its odd prefixes, then n has one or two 1's.

Proof:

Since n >= 1, n has at least one 1.
Suppose n has more than two 1's.
Then n has an odd proper prefix.
Therefore, let m be the longest odd proper prefix of n.
We can show that m > 1 and n = km + 1.
Hence m does not divide n.
Hence n is not divisible by all its odd prefixes, a contradiction.
So n has one or two 1's, QED.

Lemma 2:

If n >= 1 is divisible by all of its prefixes, then n has one or two 1's.

(Note: The numbers divisible by all their binary prefixes are given by A175381.  Gardiner's numbers are a subset, divisible by all and only their binary prefixes.)

Proof:

If n is divisible by all its prefixes, it is divisible by all its odd prefixes.
Let m be equal to n with its trailing 0's removed.
m is odd and divisible by all its odd prefixes.
By Lemma 1, m has one or two 1's.
But m and n have the same number of 1's, so n has one or two 1's, QED.

Lemma 3:

If n >= 1 is divisible by all of its prefixes, then one of:

	(a) n = 2^k where 0 <= k.
	(b) n = (2^j + 1)*2^k where 0 <= k < j.

Proof left to the reader, uses Lemma 2.

Theorem:

If the divisors of n are precisely the prefixes of n, then n is of one of the forms:

	(a) n = 2^k, where k >= 0
	(b) n = (2^(k + 1) + 1)*2^k, where k >= 0 and 2^(k + 1) + 1 is prime.

Proof left to the reader, uses Lemma 3.