5 ms·

> there is also a very elegant solution that fits in a tweet. (If you don't want to try solving it, or have tried and have given up, here is the solution I tri

by gopalv 5y ago

> there is also a very elegant solution that fits in a tweet. (If you don't want to try solving it, or have tried and have given up, here is the solution I tried to understand the tweet a couple of times, but I couldn't follow the proof from the tweet itself, so I wrote it up again with the basic axiom from the tweet as a basis + work out each step of the process. https://gist.github.com/t3rmin4t0r/a953450ac64b6868540bbce79df4e9a3 https://gist.github.com/t3rmin4t0r/a953450ac64b6868540bbce79... The original proof is elegant, because it has a single item of information (the "what") to use to solve the entire thing, but was missing the "how" for me.

kazinator 5y ago
Modulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). We show congruences using ≡, and always have (mod N) on the far right to indicate the modulus for the congurence. More generally, if ABC is a decimal string, then we know that ABC ≡ A + B + C (mod 9). Moreover ABC + DEF + GHI must be congruent to A+B+C + D+E+F + G+H+I (mod 9). And if ABC + DEF + GHI is equal to 123J, then A+B+C + D+E+F + G+H+I ≡ 123J ≡ 1+2+3+J (mod 9). Thus: A+B+C+D+E+F+G+H+I ≡ 1+2+3+J (mod 9) Now suppose we add J to both sides: A+B+C+D+E+F+G+H+I+J ≡ 1+2+3+J+J (mod 9) OK so now we know that the left hand side A+...+J contains all elements from 0 to 9, because of the problem constraint that the letters represent unique digits. The numbers 0 to 9 add together to 45. Now 45 is congruent to 0 (mod 9). Therefore: A+B+C+D+E+F+G+H+I+J ≡ 45 ≡ 0 ≡ 6 + 2J (mod 9) We no longer care about the A+..+J; it's vanished. We solve the remaining equation: 0 ≡ 6 + 2J (mod 9) If 6 + X (mod 9) is congruent to 0, X must be one of {... -6, 3, 12, 21, 30, 39 ...}: the set of integers congruent to 3, (mod 9). If X = 2J, where J is a one-digit decimal integer, X must be an even, non-negative integer. That rules out -6, 3 and 21. It can't be 30, because J can't be 15. X must be 12, which gives J = 6.
- quietbritishjim 5y ago
  That was all good, except this bit was not obvious to me: > Modulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: > For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). This is the part where the parent comment's explanation was helpful.
  - kazinator 5y ago
    There is a nice, succinct explanation for this (which relies on some intuition or knowledge of modulo arithmetic and congruences). First, a small defnition: let dsum(X) denote "sum of the digits of the decimal representation of whole number x". In the modulo 9 congruence, 0 and 9 are equivalent symbols. 9 ≡ 0 (mod 9). Though distinct integers outside of the congruence they are indistinguishable elements of the congruence. Observe that since 9 is congruent to 0, the number 10 is congruent to 1: 10 ≡ 1 (mod 9). Therefore, all powers of 10 are also congruent to 1: 1 ≡ 10 ≡ 100 ≡ 1000 ... (mod 9). Next, note that these numbers x ∈ {1, 10, 100, 1000, ...} all have the property that x ≡ dsum(X) (mod 9). The sum of decimal digits of each power of 10 is 1, and each power of 10 is congruent to 1, modulo 9. Within a congruence, whenever we multiply by any congruence element that is indistinguishable from 1, we get the same element. So all of these numbers 1, 10, 100, ... are identity elements in the modulo 9 congruence. Identity means that, for instance 7 ≡ 70 ≡ 700 ≡ 7000 = 7000 ... (mod 9). If we multiply the congruence element 7 by any power of 10, the result is congruent to 7, modulo 9, because 10 is the identity element: no matter how many times we multiply an integer by 10, the resulting integer is the same modulo 9 congruence element. (Moreover, also note that dsum(7) = dsum(70) = dsum(700) ...). Next, note that every decimal integer is formed by a sum combination of multiples of power of 10. For instance, 1234 is equal to 1 x 1000 + 2 x 100 + 3 x 10 + 4. But suppose we do this arithmetic in the modulo 9 congruence: it must necessarily be that: 1000 + 200 + 30 + 4 ≡ 1 + 2 + 3 + 4 (mod 9). This is because, individually, 1000 ≡ 1 (mod 9), and 200 ≡ 2 (mod 9), 30 = 3 (mod 9). The power of 10 factors do not matter, since they are really powers of the identity element 1 in the mod 9 congruence. The succinct explanation is then: every whole number has a decimal form made up of digits, which are multiplied by powers of 10. But in the modulo 9 congruence, powers of 10 do not matter: they map to the multiplicative identity element 1. That leaves the sum of the digits indistinguishable (in the modulo 9 congruence) from the value of the number (which is also a kind of sum of the digits, with each digit being scaled by a different power of 10).
kazinator 5y ago
I'm trying it with this TXR Lisp, just for fun. It uses an implementation of John MacCarthy's amb operator based on delimited continuations, which are slow. (defmacro amb-scope (. forms) ^(block amb-scope ,*forms)) (defun amb (. args) (suspend amb-scope cont (each ((a args)) (whenlet ((res (and a (call cont a)))) (return-from amb-scope res))))) (defmacro 0-9 () '(amb 0 1 2 3 4 5 6 7 8 9)) (defmacro val (p q r) ^(+ (* 100 ,p) (* 10 ,q) ,r)) (compile-only (amb-scope (let* ((A (0-9)) (B (0-9)) (C (0-9)) (D (0-9)) (E (0-9)) (F (0-9)) (G (0-9)) (H (0-9)) (I (0-9)) (J (0-9))) (amb (and (eql (+ (val A B C) (val D E F) (val G H I)) (+ 1230 J)) (eql 1023 (mask A B C D E F G H I J)))) (prinl (list A B C D E F G H I J))))) Every amb expression says: "I denote my leftmost non-nil argument which makes the remaining computation successful". The "remaining computation" is the future computation up to returning a value from the enclosing amb-scope form. The amb-scope form succeeds if it yields a non-nil value. We use amb to ambiguously bind A, B, C, ... to all the values from 0 to 9, amb magically selects the successful value for each one. We also use amb to express assertions. If we assert (amb (eq 'day 'night)) then that fails: night is not day. We simply assert the desired conditions over the variables. If there is any way for the conditions to be true, then that means there exist successful values for the variables and so all the prior ambs choose those successful values. This is the TXR Lisp interactive listener of TXR 272. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. Upgrade to TXR Pro for a one-time fee of learning Lisp! 1> (compile-file "abcprob") t 2> (load "abcprob") (0 1 2 3 4 5 8 7 9 6) nil Thus 012 345 879 ---- 1236 The "all letter digits unique" is efficiently met using bits to represent a set. TXR Lisp has a mask function which calculates an integer whose binary representation has a 1 in the positions indicated by the arguments. E.g (mask 0 2) yields 6, and (mask 0 1 2) yields 7. If mask is given 10 unique digit values---the complete set---it must produce the value #b1111111111 or 1023, the complete set mask. We thereby avoid n squared silliness like (and (neql A B) (neql A C) ...): asserting that no letter pair is equal.
- jonsen 5y ago
  Normally in these kind of cryptogram puzzles the leading digits of a number can't be 0. Your solution has A = 0.

by gopalv 5y ago

kazinator 5y ago

Modulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). We show congruences using ≡, and always have (mod N) on the far right to indicate the modulus for the congurence. More generally, if ABC is a decimal string, then we know that ABC ≡ A + B + C (mod 9). Moreover ABC + DEF + GHI must be congruent to A+B+C + D+E+F + G+H+I (mod 9). And if ABC + DEF + GHI is equal to 123J, then A+B+C + D+E+F + G+H+I ≡ 123J ≡ 1+2+3+J (mod 9). Thus: A+B+C+D+E+F+G+H+I ≡ 1+2+3+J (mod 9) Now suppose we add J to both sides: A+B+C+D+E+F+G+H+I+J ≡ 1+2+3+J+J (mod 9) OK so now we know that the left hand side A+...+J contains all elements from 0 to 9, because of the problem constraint that the letters represent unique digits. The numbers 0 to 9 add together to 45. Now 45 is congruent to 0 (mod 9). Therefore: A+B+C+D+E+F+G+H+I+J ≡ 45 ≡ 0 ≡ 6 + 2J (mod 9) We no longer care about the A+..+J; it's vanished. We solve the remaining equation: 0 ≡ 6 + 2J (mod 9) If 6 + X (mod 9) is congruent to 0, X must be one of {... -6, 3, 12, 21, 30, 39 ...}: the set of integers congruent to 3, (mod 9). If X = 2J, where J is a one-digit decimal integer, X must be an even, non-negative integer. That rules out -6, 3 and 21. It can't be 30, because J can't be 15. X must be 12, which gives J = 6.

quietbritishjim 5y ago
That was all good, except this bit was not obvious to me: > Modulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: > For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). This is the part where the parent comment's explanation was helpful.
- kazinator 5y ago
  There is a nice, succinct explanation for this (which relies on some intuition or knowledge of modulo arithmetic and congruences). First, a small defnition: let dsum(X) denote "sum of the digits of the decimal representation of whole number x". In the modulo 9 congruence, 0 and 9 are equivalent symbols. 9 ≡ 0 (mod 9). Though distinct integers outside of the congruence they are indistinguishable elements of the congruence. Observe that since 9 is congruent to 0, the number 10 is congruent to 1: 10 ≡ 1 (mod 9). Therefore, all powers of 10 are also congruent to 1: 1 ≡ 10 ≡ 100 ≡ 1000 ... (mod 9). Next, note that these numbers x ∈ {1, 10, 100, 1000, ...} all have the property that x ≡ dsum(X) (mod 9). The sum of decimal digits of each power of 10 is 1, and each power of 10 is congruent to 1, modulo 9. Within a congruence, whenever we multiply by any congruence element that is indistinguishable from 1, we get the same element. So all of these numbers 1, 10, 100, ... are identity elements in the modulo 9 congruence. Identity means that, for instance 7 ≡ 70 ≡ 700 ≡ 7000 = 7000 ... (mod 9). If we multiply the congruence element 7 by any power of 10, the result is congruent to 7, modulo 9, because 10 is the identity element: no matter how many times we multiply an integer by 10, the resulting integer is the same modulo 9 congruence element. (Moreover, also note that dsum(7) = dsum(70) = dsum(700) ...). Next, note that every decimal integer is formed by a sum combination of multiples of power of 10. For instance, 1234 is equal to 1 x 1000 + 2 x 100 + 3 x 10 + 4. But suppose we do this arithmetic in the modulo 9 congruence: it must necessarily be that: 1000 + 200 + 30 + 4 ≡ 1 + 2 + 3 + 4 (mod 9). This is because, individually, 1000 ≡ 1 (mod 9), and 200 ≡ 2 (mod 9), 30 = 3 (mod 9). The power of 10 factors do not matter, since they are really powers of the identity element 1 in the mod 9 congruence. The succinct explanation is then: every whole number has a decimal form made up of digits, which are multiplied by powers of 10. But in the modulo 9 congruence, powers of 10 do not matter: they map to the multiplicative identity element 1. That leaves the sum of the digits indistinguishable (in the modulo 9 congruence) from the value of the number (which is also a kind of sum of the digits, with each digit being scaled by a different power of 10).

kazinator 5y ago

I'm trying it with this TXR Lisp, just for fun. It uses an implementation of John MacCarthy's amb operator based on delimited continuations, which are slow. (defmacro amb-scope (. forms) ^(block amb-scope ,*forms)) (defun amb (. args) (suspend amb-scope cont (each ((a args)) (whenlet ((res (and a (call cont a)))) (return-from amb-scope res))))) (defmacro 0-9 () '(amb 0 1 2 3 4 5 6 7 8 9)) (defmacro val (p q r) ^(+ (* 100 ,p) (* 10 ,q) ,r)) (compile-only (amb-scope (let* ((A (0-9)) (B (0-9)) (C (0-9)) (D (0-9)) (E (0-9)) (F (0-9)) (G (0-9)) (H (0-9)) (I (0-9)) (J (0-9))) (amb (and (eql (+ (val A B C) (val D E F) (val G H I)) (+ 1230 J)) (eql 1023 (mask A B C D E F G H I J)))) (prinl (list A B C D E F G H I J))))) Every amb expression says: "I denote my leftmost non-nil argument which makes the remaining computation successful". The "remaining computation" is the future computation up to returning a value from the enclosing amb-scope form. The amb-scope form succeeds if it yields a non-nil value. We use amb to ambiguously bind A, B, C, ... to all the values from 0 to 9, amb magically selects the successful value for each one. We also use amb to express assertions. If we assert (amb (eq 'day 'night)) then that fails: night is not day. We simply assert the desired conditions over the variables. If there is any way for the conditions to be true, then that means there exist successful values for the variables and so all the prior ambs choose those successful values. This is the TXR Lisp interactive listener of TXR 272. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. Upgrade to TXR Pro for a one-time fee of learning Lisp! 1> (compile-file "abcprob") t 2> (load "abcprob") (0 1 2 3 4 5 8 7 9 6) nil Thus 012 345 879 ---- 1236 The "all letter digits unique" is efficiently met using bits to represent a set. TXR Lisp has a mask function which calculates an integer whose binary representation has a 1 in the positions indicated by the arguments. E.g (mask 0 2) yields 6, and (mask 0 1 2) yields 7. If mask is given 10 unique digit values---the complete set---it must produce the value #b1111111111 or 1023, the complete set mask. We thereby avoid n squared silliness like (and (neql A B) (neql A C) ...): asserting that no letter pair is equal.

jonsen 5y ago
Normally in these kind of cryptogram puzzles the leading digits of a number can't be 0. Your solution has A = 0.