Advertisement
Guest User

Untitled

a guest
May 21st, 2018
622
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.16 KB | None | 0 0
  1. The Freudenthal Problem:
  2.  
  3. Sam hears the sum of two numbers, Polly the product. The numbers are known to both be at least 3.
  4.  
  5. S: "You don't know the numbers"
  6. P: "That was true, but now I do"
  7. S: "Now I do too"
  8.  
  9. Classify possible pairs of numbers.
  10.  
  11.  
  12.  
  13.  
  14. Here we prove that the pair (x, y) = (2120005897729125501632512, 2261497405430902850470057) is a solution to the Freudenthal problem.
  15.  
  16.  
  17.  
  18. First statement:
  19. The sum of these values is s = 4381503303160028352102569. As s is odd, every pair of summands must be one even and one odd value. Call the even value 2a, and the odd value b. If a > 2, 2ab can factor in a valid way as either (2a, b) or (2b, a). Since s is not divisible by 3, a cannot equal b, so these are distinct factorizations. If a = 2, the summands are 4 and 4381503303160028352102565, and other valid factorizations include (20, 876300660632005670420513). This covers all possible ways to sum to s, so Sam knows Polly's number is not uniquely factorizable.
  20.  
  21.  
  22.  
  23. Second statement:
  24. The product of these values is p = 4794387837212629299206061470561348619380073693184, known to Polly. Written in terms of its prime factors, p = 2^62 * 459703 * 2261497405430902850470057. Upon hearing Sam's information, Polly can infer that s must be odd (or an exception to Goldbach's Conjecture but we will assume the conjecture holds), s - 4 must be composite, and s must not be thrice a prime. She lists the different ways to factor p such that the sum is odd. There are three:
  25.  
  26. p = (2^62 * 459703) * 2261497405430902850470057 => s ?= s1 = 4381503303160028352102569
  27. p = (2^62 * 2261497405430902850470057) * 459703 => s ?= s2 = 10429315965335508576637658380653049076450231
  28. p = (459703 * 2261497405430902850470057) * 2^62 => s ?= s3 = 1039617141773414019088064000975
  29.  
  30. None of these values are divisible by 3, so Polly must test whether s - 4 is prime or composite, for each candidate s she has. In this case, s1 - 4 is composite, while s2 - 4 and s3 - 4 are prime. As such, Sam could not have been told s2 or s3 and say the first statement, so Polly concludes the sum must be s1. It follows that the numbers are (x, y) and Polly announces that she knows the numbers.
  31.  
  32.  
  33.  
  34. Third statement:
  35. Naively, our best approach here is to consider all numbers x between 3 and 2190751651580014176051284, and perform Polly's analysis on the product a*(s-a). Polly's statement conveyed that there is only one factor sum that is consistent with the first statement, so for each x we need only find one consistent factor sum that isn't s, to prove that x is not one of the two numbers. Still, with the loop's upper bound being a 25 digit number, that could take a while.
  36.  
  37. We can take a cleverer approach. As before, we note that every sum is one even and one odd number. This time we choose to express the numbers as (2^k)a and b, and force a and b to be odd. Since s is less than 2^82, we know k is at most 81.
  38.  
  39. We have to treat the case that a > 1 and a = 1 separately.
  40.  
  41. If a > 1, then one alternate factor sum is s2 = (2^k)b + a. Computing the difference, (2^k)b + a - ((2^k)a + b) = (2^k - 1)(b - a). This alternate factor sum can thus be written as s2 = s + (2^k - 1)(b - a). This number is consistent with the first statement if s2 is odd, s2 - 4 is composite, and s2 is not thrice a prime. Since s is odd and b - a is even (being the difference of two odd numbers), we must have that s2 is odd. Showing s2 - 4 is composite is harder.
  42.  
  43. Assume k is odd. s is congruent to 2 modulo 3. In what follows, an equals sign denotes congruence modulo 3.
  44.  
  45. 2^k = 2
  46. b = s - 2*a = 2 + a
  47. s2 = 2 + (2-1)(b-a) = 2 + 2 = 1
  48. s2 - 4 = 0
  49.  
  50. In every case then, we have s2 - 4 divisible by 3. Thus, if k is odd, s2 - 4 is composite, and s2 is not a multiple of 3 because s2 is congruent to 1 modulo 3.
  51.  
  52. Thus we must have k is even. This means 2^k - 1 is a multiple of 3, so s2 - s is a multiple of 3, and thus s2 is congruent to 2 modulo 3. All that remains is to show s2 - 4 is composite, or to find a case where it is prime.
  53.  
  54. s2 - 4 differs from s - 4 by a multiple of (2^k - 1). The factorization of s - 4 is
  55.  
  56. s - 4 = 5 * 7 * 11 * 23 * 43 * 47 * 59 * 199 * 2731 * 43691 * 174763
  57.  
  58. The even values of k < 82 for which s - 4 does not have a factor in common with (2^k - 1) are only the following:
  59.  
  60. 2, 62, 74
  61.  
  62. If k = 2, consider a different alternate factor sum: s3 = 4 + ab. This number is odd, but s3 - 4 = ab is composite by construction. Modulo 3 again,
  63.  
  64. s3 - s = 4 + ab - (4a + b) = (4 - b)(1 - a)
  65. b = s - a = 2 - a
  66. s3 = 2 + (2 + a)(1 - a)
  67. s3 = 1 - a - a^2
  68.  
  69. Case a = 0:
  70. s3 = 1, not divisible by 3.
  71.  
  72. Case a = 1:
  73. s3 = 1 - 1 - 1 = 2, not divisible by 3.
  74.  
  75. Case a = 2:
  76. s3 = 1 - 2 - 1 = 1, not divisible by 3.
  77.  
  78. Thus, whenever k = 2, this alternate factor sum shows that Polly would not have been able to make her claim.
  79.  
  80. We have shown then that for Polly to make her claim, one of the two summands has to be either 2^62 times an odd number, or 2^74 times an odd number. Brute force computation from here is much more reasonable. I defined the following in Mathematica:
  81.  
  82. qqut = 4381503303160028352102569;
  83. ll = Table[{a, 2^74 # + a (qqut - 2^74 a)/# & /@ (Divisors[a (qqut - 2^74 a)][[1 ;; -2]])}, {a, 3, 231, 2}];
  84. consistent[numlist_] := AllTrue[numlist, Or[# == qqut, PrimeQ[# - 4], And[Mod[#, 3] == 0, PrimeQ[#/3]]] &]
  85. Cases[ll, {a_, l_} /; consistent[l] :> a]
  86.  
  87. The final command gives all the a such that (x,y) = ((2^74)a, s-(2^74)a) is consistent with Polly's claim. It is an empty list, so k cannot be 74. We then run the command for k = 62. This took about an hour to execute.
  88.  
  89. ll2 = Table[{a, 2^62 # + a (qqut - 2^62 a)/# & /@ (Divisors[a (qqut - 2^62 a)][[1 ;; -2]])}, {a, 3, 950087, 2}];
  90. Cases[ll2, {a_, l_} /; consistent[l] :> a]
  91.  
  92. The output is {459703}. Therefore a = 459703 is the only value of a such that (x,y) = ((2^62)a, s-(2^62)a) is consistent with Polly's claim. We have one solution pair, but we haven't eliminated every option yet. We mentioned that the case where a = 1 has to be treated separately. Indeed, our arguments regarding k were only valid if s2 was a valid alternate sum, and since one of the summands is a, it fails to hold when a = 1. Fortunately, there are only 81 cases to check to complete the proof.
  93.  
  94. If s - 2^k is prime for any k, there is only a single odd factor sum, and thus Polly's claim is consistent.
  95.  
  96. Select[Table[qqut - 2^k, {k, 1, 81}], PrimeQ]
  97.  
  98. This list is empty, so there are no primes of this form. Then we check the alternate odd factorizations for every product 2^k(s-2^k).
  99.  
  100. ll3 = Table[{k, 2^k # + (qqut - 2^k)/# & /@ (Divisors[qqut - 2^k][[1 ;; -2]])}, {k, 1, 81}];
  101. Cases[ll3, {k_, l_} /; consistent[l] :> k]
  102.  
  103. This list is empty as well, so there is no pair of numbers consistent with s and the first two statements with a = 1.
  104.  
  105. Therefore, because there is exactly one pair of values for which Polly's claim is consistent, Sam knows that these values are x and y, and so the third statement can be made.
  106.  
  107.  
  108.  
  109. This completes the proof that the pair (x, y) = (2120005897729125501632512, 2261497405430902850470057) solves the Freudenthal problem. Proving that the total number of solutions is finite, with this pair the largest by sum, is left as an exercise to the reader.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement