9-Digit Numbers

  1. Let R(X) be the number created by reversing the digits of X.  When a 9-digit Palindromic number P is divided by a 7-digit number N, a remainder of R(N) is obtained.  Also, dividing N by R(N) gives a remainder D, where D is a prime number.  The last digit of neither P nor N is zero.  Find any triplets (P,N,D) satisfying these conditions.  If in addition, the sum of the digits of D is a perfect square, how many triplets exist?

  2. Determine ten different nine digit decimal numbers beginning with the same digit, such that their sum is divisible by nine of the said numbers. How many possible solutions are there?

  3. Determine four different nine digit decimal numbers beginning with the same digit, such that their sum is divisible by three of the said numbers. How many possible solutions are there?

  4. Extension: Determine M+1 different N-digit decimal numbers beginning with the same digit, such that their sum is divisible by M of the said numbers, and N is as small as possible.  For which M<10 do solutions exist?

Source: Adapted from K Sengupta of India.  He does not yet have solutions for all of these.  Original Extension.

Solutions were received from Joseph DeVincentis for #2-4.  #1 was strictly an exercise in programming.  Denix Borris and Philippe Fondanaiche sent solutions.  Denis found 27043 triplets that meet the requirements, only 2619 of which have the digits of D sum to a square.  Philippe Fondanaiche found 2502 Solutions with the sum of D as a square.

Here are some examples

P=978343879 N=9772211 R(N)=1122779 D=789979  sod=49
P=864424468 N=8611133 R(N)=3311168 D=1988797 sod=49
P=783424387 N=7800143 R(N)=3410087 D=979969 sod=49
P=766666667 N=7642342 R(N)=2432467 D=344941 sod=25
P=674444476 N=6731231 R(N)=1321376 D=124351 sod=16

Joseph's solutions to 2-4:

M=0 and M=1 trivially fail. One number always divides itself. If the sum is divisible by one of the two numbers added to produce it, it is also divisible by the other.

For the general case, for the sum to be divisible by M of the M+1 different numbers making up the sum, it must be a different multiple of each of these numbers. But the numbers have the same number of digits and start with the same digit, so the largest is less than twice the smallest. The sum is therefore less than 2M+1 times the smallest and larger than 1 + M/2 times the largest.

But in practice, we cannot use a sum less than M times the largest, because there must be M different multiples within a range of less than a factor of 2. If M-1 is included, 2M-2 and larger multiples cannot be, and the number of different multiples M-1, M, ..., 2M-3 is only M-1 numbers. And likewise we cannot have both M and 2M in our set. So we have either M through 2M-1 or M+1 through 2M as our multiples.

For M=2, the first limit of 1 + M/2 leaves only 3 and 4 as possible multiples. A solution must have a sum S, and numbers S/3, S/4, and to make the sum work, S-S/3-S/4 = 5S/12. Equivalently, we can say the numbers are 3k, 4k, and 5k with a sum 12k. There are no two-digit solutions, but the smallest three-digit solution is from k=34: 102, 136, 170 with sum 408.

For M=3, we must have a sum multiples of either 3, 4, 5 or 4, 5, 6 of three of our numbers. Case 3, 4, 5: For sum S, the numbers are S/3, S/4, S/5, and S-S/3-S/4-S/5 = 13S/60. Alternatively, we have 12k, 13k, 15k, and 20k with sum 60k. The smallest solution is from k=9: 108 + 117 + 135 + 180 = 540 Case 4, 5, 6: The numbers are S/4, S/5, S/6, and S-S/4-S/5-S/6 = 23S/60. Since this last number is more than twice S/6, there is no solution in this category.

For M=4, the multiples are either 4, 5, 6, 7 or 5, 6, 7, 8. Case 4, 5, 6, 7: The last number is 202 S / 840. The numbers are 120k, 140k, 168k, 202k, and 210k. The smallest solution is for k=9: 1080 + 1260 + 1512 + 1818 + 1890 = 7560. Case 5, 6, 7, 8: The last number is 614 S / 1680, which is larger than twice S/8, so there is no solution in this category.

For M=5, the multiples are either 5, 6, 7, 8, 9 or 6, 7, 8, 9, 10. This time, even for the case 5, 6, 7, 8, 9 the extra number equals 3846 S / 15120 which is greater than 2*S/9 or 3360 S /15120. If you take the other set, the size of the leftover number only gets worse. The same thing happens for all larger M.

The M=3 solution also provides a solution for part 3. Since all solution sets are of the form 12k, 13k, 15k, 20k, we need simply find the k that lead to these being four nine-digit numbers starting with the same digit. Since 20/12 > 3/2 > 4/3 > ..., there are no solutions starting with 2 or larger digits; all solutions begin with 1. The k in the range 8333334 to 9999999 give appropriate sets of four numbers, so there are 1666666 solutions.

The failure for M>=5 also leads to no solution for part 2, which is simply this problem with M=9 and N=9.
Mail to Ken