02-13-2020, 08:30 AM
Post: #1
 pinkman Senior Member Posts: 433 Joined: Mar 2018
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.

02-13-2020, 05:34 PM
Post: #2
 John Keith Senior Member Posts: 1,033 Joined: Dec 2013
Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples.
02-13-2020, 06:00 PM (This post was last modified: 02-13-2020 06:06 PM by John Keith.)
Post: #3
 John Keith Senior Member Posts: 1,033 Joined: Dec 2013
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.
02-13-2020, 08:15 PM
Post: #4
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
(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
02-13-2020, 09:07 PM
Post: #5
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(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!

1452
4587
9856
3256
...
Clockwise or counterclockwise.
02-13-2020, 09:09 PM
Post: #6
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(02-13-2020 08:15 PM)Albert Chan Wrote:  gcd(2365, 2563) = 11
gcd(5698, 5896) = 22

You’re almost there! We’re looking for a prime common factor.
02-13-2020, 09:11 PM
Post: #7
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(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.
02-13-2020, 10:52 PM (This post was last modified: 02-14-2020 12:09 AM by Albert Chan.)
Post: #8
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
(02-13-2020 09:09 PM)pinkman Wrote:
(02-13-2020 08:15 PM)Albert Chan Wrote:  gcd(2365, 2563) = 11
gcd(5698, 5896) = 22

You’re almost there! We’re looking for a prime common factor.

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:
1. x + (x+1)*10 + (x-2)*100 + (x-3)*1000 ≡ x - (x+1) + (x-2) - (x-3) ≡ 0
2. x + (x-3)*10 + (x-4)*100 + (x-1)*1000 ≡ x - (x-3) + (x-4) - (x-1) ≡ 0
3. x + (x-1)*10 + (x+2)*100 + (x+3)*1000 ≡ x - (x-1) + (x+2) - (x+3) ≡ 0
4. x + (x+3)*10 + (x+4)*100 + (x+1)*1000 ≡ x - (x+3) + (x+4) - (x+1) ≡ 0

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
02-14-2020, 12:00 AM
Post: #9
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
Code:
function gcd(a, b)     if b==0 then return a end     return gcd(b, a%b) end function all_gcds()     t = {{5,4,1,2},{5,2,3,6},{5,6,9,8},{5,8,7,4}}     t_table = {__index = function(F,i) return F[1+(i-1)%4] end}     for i=1,#t do         local a = setmetatable(t[i], t_table)   -- allow wrap around         for j=1,4 do                            -- 4 corners             local d = 1000*a[j] + 10*a[j+2]             local x = d + 100*a[j+1] + a[j+3]             local y = d + 100*a[j+3] + a[j+1]             print(x,y,gcd(x,y))         end     end end

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
02-14-2020, 06:25 AM
Post: #10
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(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.

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:
1. x + (x+1)*10 + (x-2)*100 + (x-3)*1000 ≡ x - (x+1) + (x-2) - (x-3) ≡ 0
2. x + (x-3)*10 + (x-4)*100 + (x-1)*1000 ≡ x - (x-3) + (x-4) - (x-1) ≡ 0
3. x + (x-1)*10 + (x+2)*100 + (x+3)*1000 ≡ x - (x-1) + (x+2) - (x+3) ≡ 0
4. x + (x+3)*10 + (x+4)*100 + (x+1)*1000 ≡ x - (x+3) + (x+4) - (x+1) ≡ 0

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

With all my respect!
There is a generic demonstration that factors by 11 , but using congruence is very elegant.
02-14-2020, 06:45 AM (This post was last modified: 02-14-2020 06:47 AM by pinkman.)
Post: #11
 pinkman Senior Member Posts: 433 Joined: Mar 2018
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)

02-14-2020, 11:57 AM (This post was last modified: 02-14-2020 12:00 PM by Albert Chan.)
Post: #12
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
(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
02-14-2020, 12:07 PM
Post: #13
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(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)

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

Yes, good idea to better explain this step of the demonstration.
02-14-2020, 12:17 PM (This post was last modified: 02-14-2020 01:43 PM by pinkman.)
Post: #14
 pinkman Senior Member Posts: 433 Joined: Mar 2018
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.

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 = []movr = [[3], [-3,3], [-3]]      # authorized moves on each row from bottom to top (first to third)movc = [[1], [-1,1], [-1]]      # authorized moves on each column (left to right)a = 0for i in movr:                  # step accross each row...    for j in movc:              # and accross each column        a += 1                  # name (number) of the key        for k in i:             # start moving along the row            for l in j:         # and along the column                result.append(a*1000 + (a + k)*100 + (a + k + l)*10 + (a + k + l - k))        for k in j:             # then start moving along the column            for l in i:         # and along the row                result.append(a*1000 + (a + k)*100 + (a + k + l)*10 + (a + k + l - k))for i in result:    print(i, " modulo (11) -> ", i %11)

And the result :

Code:
 1452  modulo (11) ->  0 1254  modulo (11) ->  0 2541  modulo (11) ->  0 2563  modulo (11) ->  0 2145  modulo (11) ->  0 2365  modulo (11) ->  0 3652  modulo (11) ->  0 3256  modulo (11) ->  0 4125  modulo (11) ->  0 4785  modulo (11) ->  0 4521  modulo (11) ->  0 4587  modulo (11) ->  0 5214  modulo (11) ->  0 5236  modulo (11) ->  0 5874  modulo (11) ->  0 5896  modulo (11) ->  0 5412  modulo (11) ->  0 5478  modulo (11) ->  0 5632  modulo (11) ->  0 5698  modulo (11) ->  0 6325  modulo (11) ->  0 6985  modulo (11) ->  0 6523  modulo (11) ->  0 6589  modulo (11) ->  0 7458  modulo (11) ->  0 7854  modulo (11) ->  0 8547  modulo (11) ->  0 8569  modulo (11) ->  0 8745  modulo (11) ->  0 8965  modulo (11) ->  0 9658  modulo (11) ->  0 9856  modulo (11) ->  0
02-14-2020, 09:12 PM (This post was last modified: 02-14-2020 09:13 PM by John Keith.)
Post: #15
 John Keith Senior Member Posts: 1,033 Joined: Dec 2013
Ah, now I understand. For completeness, here is my HP50 version. It requires the libraries ListExt, GoferLists, and Ifactor.

Code:
 \<< { { 1 2 5 4 }       { 2 3 6 5 }       { 5 6 9 8 }       { 4 5 8 7 } } \-> s   \<< 1. 4.     FOR j 0. 1.       FOR k s j GET k 2. MOD { REV } IFT 1. 4.         START DUP NL\->I IFACTOR LGRP SWAP LROLL         NEXT DROP       NEXT     NEXT 32. \->LIST     \<< Intersect     \>> STREAM   \>> \>>
02-14-2020, 10:05 PM
Post: #16
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
(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)

Another perspective, RHS = (B+D) - (A+C), or differences of the diagonals.

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
02-14-2020, 10:55 PM (This post was last modified: 02-14-2020 10:55 PM by pinkman.)
Post: #17
 pinkman Senior Member Posts: 433 Joined: Mar 2018
(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.

Code:
 \<< { { 1 2 5 4 }       { 2 3 6 5 }       { 5 6 9 8 }       { 4 5 8 7 } } \-> s   \<< 1. 4.     FOR j 0. 1.       FOR k s j GET k 2. MOD { REV } IFT 1. 4.         START DUP NL\->I IFACTOR LGRP SWAP LROLL         NEXT DROP       NEXT     NEXT 32. \->LIST     \<< Intersect     \>> STREAM   \>> \>>

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?
02-15-2020, 06:38 PM
Post: #18
 John Keith Senior Member Posts: 1,033 Joined: Dec 2013
(02-14-2020 10:55 PM)pinkman Wrote:  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?

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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)