Correct me if I am wrong, If the given number is lets say 'p'. We have to find N such that N=(10^m-1)/9 for least m,that is divisible by 'p'.
(10^m-1)/9 = 0 (mod p) (10^m-1) = 0 (mod p) 10^m = 1 (mod p) Since the given number 'p' always ends with a 3 in its units place, 10^m and p are always co-prime. So using Fermat's Little Theorem we can calculate m = euler_totient_function(p) However you can only get a valid solution, but if we want the smalled such possible 'm', then we have to use Carmichael Function, which will give you the lowest such possible 'm'. http://math-it.org/Mathematik/Zahlentheorie/Carmichael.html On Thu, Oct 13, 2011 at 6:26 PM, Gene <gene.ress...@gmail.com> wrote: > I should have noted that this can handle inputs up to about 2^32 / (10 > * x). Run time is proportional to the number of 1's. You can also add > a bit of code to discover the digits of the multiplicand. > > I was able to verify with lisp bignums that: 25,514 1's is equal to > > 76543 * ( a 25,509 digit number ) > > An unverified one because my machine ran out of memory while > multiplying (but which took about .05 seconds to find) is: > > 1,638,726 1's = 9,876,543 times (a 1,638,719 digit number ) > > On Oct 12, 4:35 pm, Gene <gene.ress...@gmail.com> wrote: > > First note: > > > > 0 * 3 = 0 > > 7 * 3 = 21 > > 4 * 3 = 12 > > 1 * 3 = 3 > > 8 * 3 = 24 > > 5 * 3 = 15 > > 2 * 3 = 6 > > 9 * 3 = 27 > > 6 * 3 = 18 > > 3 * 3 = 9 > > > > Important is that the final digits of each line count 0 to 9. > > > > Now you can build an answer right to left. > > > > Example: 123. > > > > Check the table to get the rightmost 1. > > 7 * 123 = 861 > > > > Now you need to add ...50 to make the 10's digit a 1. So > > > > 50 * 123 = 6150 + 861 = 7011 > > > > And now add 100 to get the third 1... > > 700 * 123 = 86,100 + 7011 = 93,111 > > > > Following this pattern: > > 6000 * 123 = 738,000 + 93,111 = 831,111 > > 60000 * 123 = 7,380,000 + 831,111 = 8,211,111 > > 300000 * 123 = 36,900,000 + 8,211,111 = 45,111,111 > > > > Okay. That's enough. We stop when the carry digits finally turn out > > to be all 1's. > > > > In a program once we've arranged for a rightmost 1 we can shift it out > > of the calculation by dividing everything by 10. At the same time we > > can shift out the trailing zeros in the multiplicands. > > > > So here's a quick implementation. Sorry in advance for mistakes, but > > it seems to be working okay: > > > > #include <stdio.h> > > > > // If x is all 1's (including zero of them), return > > // how many there are. Otherwise return ~0u. > > unsigned all_ones(unsigned x) > > { > > unsigned n = 0; > > while (x) { > > if (x % 10 != 1) > > return ~0u; > > x /= 10; > > ++n; > > } > > return n; > > > > } > > > > // A table s.t. (x + 3 * mul[x % 10]) ends in 1. > > unsigned mul[] = {7,0,3,6,9,2,5,8,1,4}; > > > > // Return n s.t. x divides sum_{i=0 to n-1} 10^i . > > // x must be congruent to 3 mod 10. > > unsigned ones(unsigned x) > > { > > unsigned n, carry = x; > > for (n = 0; all_ones(carry) == ~0u; n++) { > > carry = (carry + mul[carry % 10] * x) / 10; > > // printf("%d\n", carry); > > } > > return n + all_ones(carry); > > > > } > > > > int main(void) > > { > > unsigned x; > > if (scanf("%u", &x) == 1 && x % 10 == 3) > > printf("%u divides %u 1's\n", x, ones(x)); > > return 0; > > > > } > > > > On Oct 10, 9:20 am, VIHARRI <viharri....@gmail.com> wrote: > > > > > > > > > > > > > > > > > For every number that has 3 in its units place has one multiple which > > > has all one's i.e. 111 is > > > such multiple and 13 has a multiple 111111. Write a program to find > > > such multiple for any > > > number that has 3 at its units place. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- B.Prabhat Kiran CS08B014 4th Year UnderGrad Comp Sci & Engg IIT-Madras -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
