Challenge - Keypad puzzle - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: Challenge - Keypad puzzle (/thread-14497.html) |
Challenge - Keypad puzzle - pinkman - 02-13-2020 08:30 AM Hi everyone. A small challenge discussed with a friend. Any number created by a tuple of 4 digits on a square shape of 4 consecutive keys on a standard keypad share a common prime factor. What is this common factor? The demonstration of quite easy, you can find it once you have the common factor. I also ask you to create a brut force algorithm, taking any tuple as defined above and finding the common factor. Brut force might be funny because there are not a lot of combinations and the algorithm, even if brut force, has lots of possibilities of optimization. [attachment=8089] RE: Challenge - Keypad puzzle - John Keith - 02-13-2020 05:34 PM Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples. RE: Challenge - Keypad puzzle - John Keith - 02-13-2020 06:00 PM Assuming here that you meant permutations, it seems that the two groups on the left side of the keypad, { 1 2 4 5 } and { 4 5 7 8 } share the same common factor. However, the two groups on the right hand side, { 2 3 5 6 } and { 5 6 8 9 } do not share the same common factor nor any others. Maybe I am missing something? Another amusing observation: the "almost square" formed by the digits { 0 1 2 } on the lower left (ignoring the decimal point) share the same common factor as the other two groups on the left side. RE: Challenge - Keypad puzzle - Albert Chan - 02-13-2020 08:15 PM (02-13-2020 06:00 PM)John Keith Wrote: However, the two groups on the right hand side, { 2 3 5 6 } and { 5 6 8 9 } do not share the same common factor nor any others. It may be the puzzle only allow clockwise or counter-clockwise only ? gcd(2365, 2563) = 11 gcd(5698, 5896) = 22 RE: Challenge - Keypad puzzle - pinkman - 02-13-2020 09:07 PM (02-13-2020 05:34 PM)John Keith Wrote: Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples. Sorry I was at work! Just follow a square, like: 1452 4587 9856 3256 ... Clockwise or counterclockwise. RE: Challenge - Keypad puzzle - pinkman - 02-13-2020 09:09 PM (02-13-2020 08:15 PM)Albert Chan Wrote: gcd(2365, 2563) = 11 You’re almost there! We’re looking for a prime common factor. RE: Challenge - Keypad puzzle - pinkman - 02-13-2020 09:11 PM (02-13-2020 08:15 PM)Albert Chan Wrote: It may be the puzzle only allow clockwise or counter-clockwise only ? Both. It doesn’t matter. RE: Challenge - Keypad puzzle - Albert Chan - 02-13-2020 10:52 PM (02-13-2020 09:09 PM)pinkman Wrote:(02-13-2020 08:15 PM)Albert Chan Wrote: gcd(2365, 2563) = 11 From above 1 case, the common prime factor is 11. To prove, say, "counter-clockwise" number is divisible by 11 Modulo 11, for least significant digits, say x, at the 4 corners:
For the "clockwise" numbers, just imagine the weight of 1,10,100,1000 are reversed. Modulo 11, we still get the RHS result, since 100≡1, 1000≡10≡-1 RE: Challenge - Keypad puzzle - Albert Chan - 02-14-2020 12:00 AM Code: function gcd(a, b) Above is my brute-force Lua code. Only 16 cases, all of them included the "5", common prime factor = 11 lua> all_gcds() 5412 5214 66 4125 4521 33 1254 1452 66 2541 2145 33 5236 5632 44 2365 2563 11 3652 3256 44 6523 6325 11 5698 5896 22 6985 6589 11 9856 9658 22 8569 8965 11 5874 5478 66 8745 8547 33 7458 7854 66 4587 4785 33 RE: Challenge - Keypad puzzle - pinkman - 02-14-2020 06:25 AM (02-13-2020 10:52 PM)Albert Chan Wrote:(02-13-2020 09:09 PM)pinkman Wrote: You’re almost there! We’re looking for a prime common factor. With all my respect! There is a generic demonstration that factors by 11 , but using congruence is very elegant. RE: Challenge - Keypad puzzle - pinkman - 02-14-2020 06:45 AM Following Albert’s idea using congruence: Because: 1000≡-1 (mod 11) 100≡1 (mod 11) 10≡-1 (mod 11) 1≡1 (mod 11) Then: A*1000+B*100+C*10+D≡-A+B-C+D (mod 11) -A+B-C+D=-(A-B+C-D)=0 because the sum of the subtraction of vertices is always 0. So : A*1000+B*100+C*10+D≡0 (mod 11) Original idea and demonstration: https://twitter.com/fermatslibrary/status/1227583470320455681?s=21 RE: Challenge - Keypad puzzle - Albert Chan - 02-14-2020 11:57 AM (02-14-2020 06:45 AM)pinkman Wrote: A*1000+B*100+C*10+D≡-A+B-C+D (mod 11) Another perspective, RHS = (B+D) - (A+C), or differences of the diagonals. For the keypad (or its rotations, or flipped over) 7 8 9 4 5 6 1 2 3 For any 2x2 squares, diagonals sum to the same number, thus (B+D) - (A+C) = 0 RE: Challenge - Keypad puzzle - pinkman - 02-14-2020 12:07 PM (02-14-2020 11:57 AM)Albert Chan Wrote:(02-14-2020 06:45 AM)pinkman Wrote: A*1000+B*100+C*10+D≡-A+B-C+D (mod 11) Yes, good idea to better explain this step of the demonstration. RE: Challenge - Keypad puzzle - pinkman - 02-14-2020 12:17 PM I still haven't finished a clean implementation in HPPL, but I think I found an elegant solution in python. Elegant but brut force (find all numbers and divide them by 11) as I requested. A few preliminary comments about the methods: What I call a 'move' is the path followed by your finger on the keypad between 2 keys. Suppose you start from the '5' key (coordinates 2x2 on the grid) : you have 8 possible moves : 4 (left, right, up, down) x 2 (clockwise and counter-clockwise). Starting from other keys reduces the number of authorized moves, but the principle is the same. A move from '5' key is -1 ('4' key), +1 ('6' key), -3 ('2' key) or +3 ('8' key). To find the number formed by the square, you make 3 moves after having used the initial key, which makes 4 digits. After a horizontal move (+/-1) you have to make a vertical move (+/-3), and then an horizontal move in the opposite direction of the previous horizontal one, then a vertical move in the opposite direction of the previous vertical one. Mathematically there are two properties to follow a consecutive square on the keypad : 1- If we call m our first move (being -1, +1, -3 or +3), then the third move is -m. 2- If we call m' our second move (being -1, +1, -3, +3), then you'll have ton constraint |m|≠|m'| (in readable language: +/-1 is followed by +/-3, +/-3 is followed by +/-1). For each key, the moves are m, m', -m. PHP Code: result = [] And the result : Code:
RE: Challenge - Keypad puzzle - John Keith - 02-14-2020 09:12 PM Ah, now I understand. For completeness, here is my HP50 version. It requires the libraries ListExt, GoferLists, and Ifactor. Code:
RE: Challenge - Keypad puzzle - Albert Chan - 02-14-2020 10:05 PM (02-14-2020 11:57 AM)Albert Chan Wrote:(02-14-2020 06:45 AM)pinkman Wrote: A*1000+B*100+C*10+D≡-A+B-C+D (mod 11) Here is another, with geometry. sum of diagonals, if divided by 2, is their mid-point, say point M M = (B+D)/2 = (A+C)/2 RHS = (B+D) - (A+C) = 2M - 2M = 0 RE: Challenge - Keypad puzzle - pinkman - 02-14-2020 10:55 PM (02-14-2020 09:12 PM)John Keith Wrote: Ah, now I understand. For completeness, here is my HP50 version. It requires the libraries ListExt, GoferLists, and Ifactor. Nice! I don’t have a 50g so I could not try this: instead of hard coding ‘32’, could’nt it be counted during the loops? RE: Challenge - Keypad puzzle - John Keith - 02-15-2020 06:38 PM (02-14-2020 10:55 PM)pinkman Wrote: Nice! 32 is the total number of time the loops are executed. Counting them would waste precious machine cycles on an old, slow machine. Mostly it's just a quick-and-dirty program, unworthy of much optimization IMHO. |