All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Palindromes and Divisibility (Posted on 2015-10-16)
How many positive palindromes less than 20150 are divisible by 7?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 analytic solution | Comment 2 of 3 |
There are 46 such palindromes.

It's helpful to consider each digit count from 1 to 5 separately.

7 is the only 1-digit palindrom divisible by 7. (I'm assuming numbers must be positive and not have leading zeros.)

All 2-digit palindromes are 11 times a one-digit number. If the product is divisible by 7, then it must come from the one-digit number, so 77 is the only 2-digit solution.

All 3-digit palindromes aba can be written as 101a + 10b = 3a + 3b mod 7, so these numbers are divisible by 7 when 3a + 3b is divisible by 7. But we can factor that as 3(a+b) and using the same logic as in the previous case conclude that a+b is divisible by 7. Practically, that means a+b = 7 or a+b=14.

a+b = 7 gives (1,6), (2,5) and (3,4), each of which produces a pair of solutions depending on which is a and which b:
a+b = 14 gives (7,7), (8,6), (9,5) which gives only 5 solutions, since 777 is degenerate. That's a total of 11 3-digit solutions.

All 4-digit palindromes abba can be written as 1001a + 110b. but 1001 is a multiple of 7 already, so that's equal to 5b mod 7. This sum is divisible by 7 when b is divisible by 7, regardless of a. So among 4-digit numbers, a is in (1,2,3,4,5,6,7,8,9) and b in (0,7), for another 18 solutions.

Now the 5-digit numbers. First, given the limit 20150, the only possible palindromes beginning with 2 are 20002 and 20102, neither of which are divisible by 7. So we only have to count 5-digit numbers beginning with 1, of the form 1aba1

A similar approach yields that 10001 + 1010a + 100b must be divisible by 7, which is equal to 5 + 2(a+b)
so 2(a+b) must be equal to 2 mod 7, and (a+b) must be equal to 1. That is, a+b = 1 or a+b = 8 or a+b = 15 are solutions

a+b = 1 gives (0,1), and as before a and b are interchangeable so there are two solutions here. a+b = 8 gives (0,8), (1,7), (2,6), (3,5) and the degenerate (4,4) which gives a total of 9 solutions. And a+b=15 gives (6,9) and (8,7) for another 4 solutions, and a total of 15 five-digit solutions.

The grand total, then is 1 + 1 + 11 + 18 + 15 = 46 solutions:

7
77
161
252
343
434
525
595
616
686
777
868
959
1001
1771
2002
2772
3003
3773
4004
4774
5005
5775
6006
6776
7007
7777
8008
8778
9009
9779
10101
10801
11011
11711
12621
13531
14441
15351
16261
16961
17171
17871
18081
18781
19691

Eyeballing, this appears to be consistent with Charlie's exhaustive computer analysis, which is certainly encouraging.
 Posted by Paul on 2015-10-16 12:16:55

 Search: Search body:
Forums (0)