Puzzle - RPL and others
05-09-2021, 01:21 AM
Post: #33
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
(05-07-2021 04:17 PM)3298 Wrote:  On the laptop, 60 is still rescued by the large number of small buckets and processes in about a second.

The idea of getting buckets from gcd(2n,d) does not have much to back it up.

Buckets from gcd(n, d) does, based on successive removal from set of digits {1 to n-1}
This is how we get the non-buckets. (removal of all multiples, i.e. coprime to n)

Mod-4 rule is also easy to show. We only need 2 digits.

If n = 4k:
d3*(4k) + d4 = 0 (mod 4)
d4 = 0 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d4 = d8 = d12 = ... = 0 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d2 = d6 = d10 = ... = 2 (mod 4)

If n = 4k+2:
d3*(4k+2) + d4 = 0 (mod 4)
2*d3 + d4 = 0 (mod 4)
d4/2 = -d3 = 1 (mod 2)
d4 = 2 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d4 = d8 = d12 = ... = 2 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d2 = d6 = d10 = ... = 0 (mod 4)

This generalized to invariant (even n, even k): n + k + dk ≡ 0 (mod 4)

---

I tried to see the difference of gcd(n,d) vs gcd(2n,d), and this affect more than 1 bucket.

Code:
from gmpy2 import gcd def bucket(n, k=1):     b = {}     for i,x in enumerate(gcd(n*k,d) for d in range(n)):             b.setdefault(x, []).append(i)     for i in sorted(b)[:-1]: print i, b[i]

>>> bucket(60)
1 [1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59]
2 [2, 14, 22, 26, 34, 38, 46, 58]
3 [3, 9, 21, 27, 33, 39, 51, 57]
4 [4, 8, 16, 28, 32, 44, 52, 56]
5 [5, 25, 35, 55]
6 [6, 18, 42, 54]
10 [10, 50]
12 [12, 24, 36, 48]
15 [15, 45]
20 [20, 40]
30 [30]

>>> bucket(60,2)
1 [1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59]
2 [2, 14, 22, 26, 34, 38, 46, 58]
3 [3, 9, 21, 27, 33, 39, 51, 57]
4 [4, 28, 44, 52]
5 [5, 25, 35, 55]
6 [6, 18, 42, 54]
8 [8, 16, 32, 56]
10 [10, 50]
12 [12, 36]
15 [15, 45]
20 [20]
24 [24, 48]
30 [30]
40 [40]

We have 3 splits, how to apply the rules ?

Bucket 4 had splitted to 4 + 8
Bucket 12 had splitted to 12 + 24
Bucket 20 splitted to 20 + 40

And more importantly, is it even correct to "swap" buckets ?
You might need to show this is always true, before adding it to the code ...
 « Next Oldest | Next Newest »

 Messages In This Thread Puzzle - RPL and others - Gene - 04-22-2021, 06:55 PM RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021, 11:52 PM RE: Puzzle - RPL and others - rprosperi - 04-23-2021, 04:21 PM RE: Puzzle - RPL and others - EdS2 - 04-23-2021, 07:30 AM RE: Puzzle - RPL and others - Dave Britten - 04-23-2021, 12:06 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:17 AM RE: Puzzle - RPL and others - ijabbott - 04-23-2021, 03:57 PM RE: Puzzle - RPL and others - Albert Chan - 04-23-2021, 04:08 PM RE: Puzzle - RPL and others - Albert Chan - 04-27-2021, 12:14 PM RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021, 04:23 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:05 PM RE: Puzzle - RPL and others - C.Ret - 04-24-2021, 04:40 PM RE: Puzzle - RPL and others - C.Ret - 04-25-2021, 09:25 AM RE: Puzzle - RPL and others - Claudio L. - 04-26-2021, 04:56 PM RE: Puzzle - RPL and others - 3298 - 04-27-2021, 08:16 PM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 02:33 AM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 03:30 AM RE: Puzzle - RPL and others - 3298 - 04-28-2021, 10:14 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 03:25 AM RE: Puzzle - RPL and others - Allen - 04-28-2021, 08:45 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 05:16 PM RE: Puzzle - RPL and others - Allen - 04-29-2021, 07:03 PM RE: Puzzle - RPL and others - C.Ret - 05-02-2021, 06:40 AM RE: Puzzle - RPL and others - 3298 - 05-03-2021, 03:43 PM RE: Puzzle - RPL and others - Albert Chan - 05-04-2021, 03:29 AM RE: Puzzle - RPL and others - 3298 - 05-04-2021, 06:48 AM RE: Puzzle - RPL and others - Albert Chan - 05-05-2021, 06:29 PM RE: Puzzle - RPL and others - 3298 - 05-06-2021, 04:24 PM RE: Puzzle - RPL and others - Albert Chan - 05-06-2021, 09:09 PM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 10:35 AM RE: Puzzle - RPL and others - 3298 - 05-07-2021, 04:17 PM RE: Puzzle - RPL and others - Albert Chan - 05-09-2021 01:21 AM RE: Puzzle - RPL and others - 3298 - 05-09-2021, 01:39 PM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 03:57 AM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 02:56 AM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 05:13 PM RE: Puzzle - RPL and others - 3298 - 05-10-2021, 08:23 PM RE: Puzzle - RPL and others - Albert Chan - 05-11-2021, 11:58 AM RE: Puzzle - RPL and others - 3298 - 05-11-2021, 02:14 PM RE: Puzzle - RPL and others - John Keith - 05-11-2021, 03:55 PM RE: Puzzle - RPL and others - ijabbott - 05-11-2021, 10:37 PM RE: Puzzle - RPL and others - Albert Chan - 05-13-2021, 11:38 PM

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