#3:
Before I begin, I will say there is one assumption I've made: that since 3 and 5 both have two bits, then 3*5 will result in 15 with four bits. Therefore, any modification to 15 that would result in 15 with fewer than four 1s, would result in 3 and/or 5 having one 1. So, in order to prove all multiples of 15 have at least four 1s, I prove that all multiples of 3 and 5 have at least two 1s.
All multiples of 15 can be expressed as 15*x. It can further be broken down as even multiples (where x = 2n) and odd multiples (where x = 2n+1).
even:
2n15 = 2*3*5*n
for an even multiple of 15 to not have four bits, one of the following must be true:
5n=2^x or 3n=2^x, because one of the factors of 15 must have only one bit.
5n=2^x:
For 5 to be a factor of 2^x, 2^x must have a 0 or 5 in the ones column (decimal)
2^x:
A pattern for the ones column appears: it repeatedly progresses through 2, 4, 8, and 6. Since the ones column can't have a 0 or 5, 5n != 2^x.
3n=2^x:
For 3 to be a factor of 2^x, 3n must have only one 1 in it, so we want to prove that 3n will have 2 or more 1s.
3n:
000 011
000 110
001 001
001 100
001 111
010 010
010 101
011 000
011 011
011 110
100 001
100 100
100 111
101 010
101 101
110 000
110 011
Looking at the 3 right furthest bits, a pattern emerges: 011, 110, 001, 100, 111, 010, 101, and 000. The only time that a multiple of 3 can have only one 1, is every 8th multiple. So we need to prove 3*8n will always have two or more 1s.
3*8n = 3*4*2n = 12*2n:
Code:
12 0001 100
24 0011 000 2*12
36 0100 100
48 0110 000 2*24
60 0111 100
72 1001 000 2*36
84 1010 100
96 1100 000 2*48
Again, looking at the 3 right furthest bits, a pattern emerges: 100 and 000. For every multiple that has a 000 as its three right most bits, it is two times a previous multiple; since the previous multiple has at least two 1s, the current multiple also has two 1s.
Therefore, 3n != 2^x. Since 3n != 2^x and 5n != 2^x, even multiples of 15 will have at least four 1s.
odd:
(2n+1)15 = (2n+1)3*5, (2n+1)3 = n_1, (2n+1)5 = n_2
For an odd multiple of 15 to not have four bits one of the following must be true:
5n_1=2^x or 3n_2=2^x, because one of the factors of 15 must have only one bit.
Since 5n_1 != 2^x and 3n_2 != 2^x has already been proven above, odd multiples of 15 will have at least four 1s.
Since odd and even multiples of 15 have at least four 1s, all multiples of 15 have at least four 1s.