P is a positive decimal (base 10) integer consisting entirely of the digit 3, and Q is a positive decimal integer consisting entirely of the digit 7. In the base-10 expansion of P*Q, the digit 3 is repeated precisely three times and the digit 7 is repeated precisely seven times. The product P*Q may consist of other digits besides 3 and 7.

Given that N is the minimum value of P*Q, determine the remainder when N is divided by 37.

Note: Try to derive a non computer assisted method, although computer programs/spreadsheet solutions are welcome.

For the following, a subscripted number preceding the bracketed base digit(s) will represent the occurance of the base digit(s) that number of times, e.g. ₃[123] = 123123123 ; and || indicates the concatenation of the digits, e.g., 123 || 45 = 12345.

We are given P as 3 x _a[1] and Q as 7 x _b[1], such that a and b are integers > 0. Such that b >= a, where the number before the colon represents the value of a, the pattern following the colon is that of the number 3 x 7 x _a[1] x _b[1]

  1 : 2 || ₀[592] ||    || _b-a[3] ||    || ₀[047] || 1
  2 : 2 || ₀[592] || 5  || _b-a[6] ||  7 || ₀[047] || 1
  3 : 2 || ₀[592] || 58 || _b-a[9] || 47 || ₀[047] || 1
  4 : 2 || ₁[592] ||    || _b-a[3] ||    || ₁[047] || 1
  5 : 2 || ₁[592] || 5  || _b-a[6] ||  7 || ₁[047] || 1
  6 : 2 || ₁[592] || 58 || _b-a[9] || 47 || ₁[047] || 1
  7 : 2 || ₂[592] ||    || _b-a[3] ||    || ₂[047] || 1
  8 : 2 || ₂[592] || 5  || _b-a[6] ||  7 || ₂[047] || 1
  9 : 2 || ₂[592] || 58 || _b-a[9] || 47 || ₂[047] || 1
...
 20 : 2 || ₇[592] || 5  || _b-a[6] ||  7 || ₇[047] || 1
 21 : 2 || ₇[592] || 58 || _b-a[9] || 47 || ₇[047] || 1
 22 : 2 || ₇[592] ||    || _b-a[3] ||    || ₇[047] || 1
etc.

Therefore, for P and Q, the a and b for N must be 22 and 25 for three 3s and seven 7s resulting in 25925925925925925925923330740740740740740740741.
The remainder of N/37 is 21, i.e., (3 x 7).

Edited on November 3, 2008, 7:33 am

Posted by Dej Mar on 2008-11-03 07:13:11