Another "base" problem. Why do they have to be so interesting (sometimes)? The following assumes N is not a multiple of 10. Let M be the sequence of multipliers. If N is not bounded above, then we cannot determine N using a finite set of multipliers, which is to say, M must be infinite. For suppose M were finite. Then there is some largest multiplier M_max in M, let M_max have d digits. Now let N1 = 10^d + 1 and N2 = 10^(d+1) + 1. Then, for all M_k in M, we have digit_sum(M_k*N1) = digit_sum(M_k*N2) = 2*digit_sum(M_k). Thus there is no multiplier Mk that can be used to distinguish between N1 and N2, and M must be infinite to distinguish any two N >= 0. If N is bounded above, you can apparently do much better. For instance, M1 = 684170684 is the smallest multiplier that can be used to distinguish between any two N <= 39. Multiplier M1 = 2^8023 can be used to distinguish between any two N with 2-digits (indeed any two N <= 105), undoubtedly there are much smaller M1 with this property. The obvious conjecture is that for any bound N_max, there exists some (huge) multiplier M1 that distinguishes between any two N <= N_max. If true, you can do much better than checking each multiplier M = (1, 2, 3, ...), you can just check M1. The hard part would be recovering N from digit_sum(M1*N).
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of rcs@xmission.com Sent: Wednesday, June 08, 2016 11:56 PM To: math-fun@mailman.xmission.com Cc: rcs@xmission.com Subject: [math-fun] another hidden number problem
Here's another hidden number problem to play with.
I have a secret number (positive integer) N. N is not a multiple of 10. I tell you the sum of the digits, and perhaps an upper bound. You give me a multiplier M1. I tell you the digit sum of M1*N. You give me M2, I tell you the digit sum of M2*N. Etc. Eventually, you guess the number.
Puzzles: Can you determine a unique N? Is there a better strategy than just using 2,3,4,... for Mi? For ten-digit N, a program can run through all the possibilities consistent with the current state-of-play. But What if N is twenty or thirty digits? Is there some non-enumerative algorithm that's more efficient for finding N?
Extra credit: N^Mi instead of Mi*N.
I've had some ideas about this puzzle, but nothing I'd call a solution.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun