Whoops2
For any natural number N that is not divisible by 2 or 5, there always exists a natural number M such that M <= N and (10^M-1)/9 is divisible by N.
2 Likes
Proof
Let An = (10^n-1)/9. Suppose that A1, A2, A3, … , AN are not divisible by N. Select i and j such that 1<=i<j<=N. Aj-Ai = A(j-i) * 10^i . Because 2, 5 and A(j-i) are not divisible by N, (Aj-Ai) modulo N is not zero. Hence, A1, A2, A3, … , AN modulo N are mutually inequivalent. As any natural number modulo N should be in the range of 0 to N-1, there are only N choices. So one of A1, … ,AN modulo N must equals to zero and it clashes with our assumption.
3 Likes
Another follow-up math problem:
Let N be any prime number that is larger than 3. Are the prime factors of (10^N-1)/9 always congruent to 1 (modulo N)?
4 Likes
It’s also a much smaller space!
# board states <3^361 = 10^172
# games with less than 150 moves ~
∑i=0150(361! / (361 - i)!) = 6e367
I think the biggest surprise to me is how uncommon legal positions are (about 1 in 81). I guess that’s because for early game, it’s hard to produce an illegal position. In the end game, there are many more opportunities to play illegal moves!
I don't know?
The number itself is congruent to 1 mod N, using that N is prime and fermat’s little theorem 10^N≡10 mod N.
But after that I can’t tell if it would be likely or not to have all factors congruent to 1 mod N. The other option is just having each factor being the multiplicative inverse of another factor or combination of factors mod N.
It seems to get tricky to find a counter example, since an increasing number of ones is turning into a sizeable number. Factoring (10^53-1)/9 seemed to be quite slow.
Is it supposed to be an easy proof?
Is it following from Repunit - Wikipedia
- If p is an odd prime, then every prime q that divides R p(b) must be either 1 plus a multiple of 2p, or a factor of b − 1. For example, a prime factor of R 29 is 62003 = 1 + 2·29·1069. The reason is that the prime p is the smallest exponent greater than 1 such that q divides bp − 1, because p is prime. Therefore, unless q divides b − 1, p divides the Carmichael function of q, which is even and equal to q − 1.
1 Like
I don’t know if the solution would be considered easy tbh.
Project Glunkolin #1
(Is this a thing now? I mean, it’s good for keeping track of them problems)
Solution
The answer is yes.
Let’s call r(M) = (10^M - 1) / 9, that is to say, the repunit of length M.
As pointed out before, r(N) ≡ 1 mod N if N is prime ≠ 3.
This can be shown using Fermat’s Theorem for all cases other than N = 2 and N = 5; these two remaining primes can trivially be checked by hand. N ≠ 3 is necessary for 9 to have a modular inverse.
Now, let N be a prime greater than 3, and let P be a prime such that P divides r(N).
Notice that P ≠ 2 and P ≠ 5, which follows from r(N) being a repunit.
Also notice that P ≠ 3 because, applying the divisibility by 3 rule, if 3 divides r(N) then 3 divides N.
By Fermat’s Theorem 10^(P-1) ≡ 1 mod P, whence P divides r(P-1).
Since P divides r(N) and P divides r(P-1), then P divides r(gcd(N, P-1)).
This follows from a similar proof the one provided by Glunkolin. That is, you subtract one repunit from the other and then forsake the zeroes (because P is not 2 or 5). So you get the repunit of the difference but, following Euclid’s algorithm, you can further simplify down to the gcd (Greatest Common Divisor).
Now let’s calculate gcd(N, P-1). Since N is prime, there are only two cases:
-
gcd(N, P-1) = 1. That would mean P divides r(1) = 1 which is impossible.
-
gcd(N, P-1) = N. This is only possible if N divides P-1. In other words P ≡ 1 mod N □
4 Likes
I’d say go for it.
Is this a spoiler? I don't know
Insider information: Monopoly seems to have the most controversial forum thread out of all that I’ve read so far. Normally people seem to agree on each other’s calculations, but not here so 
I guess exactness is not that important?
However, my gut says I’d keep the 3 doubles rule for this one. There’s a reasonable chance of that happening with 4 sided dice (1/64 as opposed to 1/216, seems enough to change a 3rd significant digit at least).
In Sudoku I never used the top 3 digit shortcut (even though I thought of it). I’m pretty sure that extra coding effort would not have been worth a few precious milliseconds. Come to think of it, the extra ifs might actually have made it slower.
At some point I did consider solving all of them by hand, though. I guess this is technically pencil&paper-able. The main issue with that approach is just the lack of a decent interface.
Discussion of 84 and 96
Sorry, I don’t mean to drop the 3 doubles rule altogether. I guess that might significantly affect the jail visit probability, which also have knock-on affects on the visit probabilities of the subsequent squares. I just meant taking a lazy, approximate shortcut of not tracking whether the last two rolls were doubles, and instead of just immediately rolling for a 1/16 chance of going to jail when the current roll is a doubles. That’s just a extremely lazy hack, and maybe the approximation is close enough. However, it’s also not that much typing to just track the last two rolls, and I’ve probably spent more time typing out this paragraph than would be saved by doing it properly… which I’ll probably anyways do when I finally get around to solving the problem. It seems that the most tedious part of this problem is just coding up all of those Chance card rules.
Again, just pure laziness. It’s not about speeding up the code, but rather speeding up the effort. Originally, I was hoping that a super simple partial solver might actually fill in enough of most problems to make it quicker (in terms of overall wall-clock time including code development time) to just do that and solve the remaining few manually. Hence, that’s why I was thinking to check if the first 3 digits were solved, not to terminate a general solver early, but to avoid writing the general solver at all.
However, ultimately, I just wrote a basic general solver. It was actually less tedious and more fun than I imagined that it would be, and not really that time consuming to code up in a bit of free time today. In the end, I think I saved a lot of time overall by avoiding any manual solving.
Code for problem 96 Sudoku
import fileinput
import numpy as np
hints = []
current = None
for line in fileinput.input(files='p096_sudoku.txt'):
line = line.rstrip()
if line[0] == 'G':
if current is not None:
hints.append(np.vstack(current))
current = []
else:
current.append(np.asarray([int(c) for c in line]))
hints.append(np.vstack(current))
def update_possible(possible, i, j, h):
for k in range(9):
if k != i:
possible[k, j, h] = 0
if k != j:
possible[i, k, h] = 0
base_x = (i // 3) * 3
base_y = (j // 3) * 3
for near_i in range(base_x, base_x + 3):
for near_j in range(base_y, base_y + 3):
if near_i != i or near_j != j:
possible[near_i, near_j, h] = 0
def init_possible(hints):
possible = np.ones((9, 9, 10), dtype=int)
possible[:, :, 0] = 0 # Unused for indexing convenience
for i in range(9):
for j in range(9):
h = hints[i, j]
if h:
possible[i, j, :] = 0
possible[i, j, h] = 1
update_possible(possible, i, j, h)
return possible
def update_hints(possible, hints):
flag = True
while flag:
flag = False
for i in range(9):
for j in range(9):
if np.sum(possible[i, j, :]) == 0:
return False # Contradiction found
if np.sum(possible[i, j, :]) == 1 and hints[i, j] == 0:
h = np.argmax(possible[i, j, :])
hints[i, j] = h
update_possible(possible, i, j, h)
flag = True
return True # Converged successfully
def pick_guess(hints, possible):
locations = []
for i in range(9):
for j in range(9):
if hints[i, j] == 0:
locations.append((i, j))
(i, j) = locations[np.random.randint(len(locations))]
values = np.arange(10)[possible[i, j, :] == 1]
return i, j, np.random.choice(values)
def solve(hints=hints[0], possible=None):
hints = hints.copy()
if possible is None:
possible = init_possible(hints)
while update_hints(possible, hints): # Simple deduction
if np.min(hints) > 0:
return hints # Solved
# Random guess w/ backtracking
i, j, h = pick_guess(hints, possible)
hypo = possible.copy()
hypo[i, j, :] = 0
hypo[i, j, h] = 1
trial = solve(hints, hypo)
if trial is False:
# Eliminate guess if failed
possible[i, j, h] = 0
else:
# Solution found
return trial
return False # Failed to solve
count = 0
answer = 0
for i, puzzle in enumerate(hints):
print("Solving", i + 1)
print(puzzle)
solution = solve(puzzle)
if solution is not False:
print(solution)
answer += 100 * solution[0, 0] + 10 * solution[0, 1] + solution[0, 2]
else:
count += 1
print("Unsolved:", count)
print(answer)
It’s relatively simple approach, but not super fast, taking about a minute or two depending on the random guessing. I imagine that adding some heuristics for picking which cell to guess, and some more advanced forward deduction rules would help speed it up a lot, but then again, it seems that there are other much more sophisticated approaches that are much faster.
1 Like
Continued discussion on 84 and 96
You cleared 96, nice! If I understood your code correctly, you make one pass of basic elimination (“naked singles”) and then random brute-force branching?
That is similar to what I did. The only extra thing is that I coded “hidden singles” as well. As for the branching, I always chose the cells with the fewest options first. I don’t know why, but with those two things my particular algorithm solves it in less than a second.
Oh, actually there is one extra thing. I avoided arrays on each cell by using ints as a binary masks. That probably makes copying the current state a bit faster.
However, don’t ask me about such trivialities as “development time”; rude. 
You should read the latest post on that problem’s thread, from some kid who watches too much Cracking the Cryptic.
I see. This could… actually work? 
I had not understood what you meant before.
I looked back into my own code, and it seems that I have 3 different files for problem 84 (the first 2 were failed attempts), all 3 of them last modified on completely different dates. The third file was quite uncharacteristic of myself, short and concise. It is clear that I was a bit frustrated at that point just gave up anything non-essential, kind of my own version of angry coding.
Anyway, the chance cards do make the bulk of the program, but it’s not absolutely terrible. I made them in separate functions, which are 1 line each (except for Next Utility, which for some reason feels the need to always be the worst Monopoly card ever 
).
1 Like
If people have given up on the PE in order, I probably will too.
Since talk of solving sudoku came up…
There was a Facebook page that I believe belongs to some kind of indie game studio (error 300) that would post puzzles for what I believe was promotion and steam keys for their game Mosaic Chronicles on Steam
I think some of them one probably would want to program a solver to do unless one is really good at that type of puzzle.
E.g. from 2 days ago where you’ve to shade in boxes corresponding to each number, and the number tells you how many consecutive boxes to share and it implies gaps. That is a 2,1 would mean two boxes beside each other, some gap, and one box shaded. I made a start on this type of solver before but I didn’t get it working.
If you want an example of a finished one I believe they gave the following simpler one, which could be a test of some solver code
They do other puzzles as well. I previously solved
Again the answer was a steam key, but it was gone anyway by the time I wrote a solver a day or two later.
Still interesting though, if that floats any ones boat.
2 Likes
Further discussion of 96
It does the simplest logical elimination method (“naked singles”), and then makes a random guess, but then it does logical elimination again, and it continues to alternate back and forth between logical elimination and random guessing. During logical elimination, it would either: 1) find the correct solution, 2) find a contradiction, which reverts the last guess and confirms that guess as another elimination, or 3) get stuck without further progress, which forces it to make another guess. I don’t think that’s quite that same thing as a pure brute-force method.
I think this is essentially a highly simplified version of how I solve Sudoku puzzles manually, with a lot of additional heuristics pruned away simply for coding laziness. In manual solves, I also look for hidden singles and other elimination tricks, and I make guesses by picking something that would appear to have the most further implications (to either quickly find a contradiction or a solution). However, coding all of that up seemed like a chore.
This seems like the most obvious improvement one could make to my approach. I was frankly too lazy to even sort the candidate guesses by some heuristic, so I just chose randomly instead. However, out of curiosity, I made a slight change to my code posted earlier, just to pick a guess on the cell with not just the fewest possibilities itself, but also the fewest total possibilities across its row, column, and box. This method also counts the cell itself three times (mainly due to the lazy way that I coded it, but we can think of that as another heuristic that gives more weight to the cell itself). Just this one change alone sped up my code to run in about 1.4 seconds (deterministically) vs a minute or two (randomly).
Here is the changed pick_guess code:
def pick_guess(hints, possible):
best_location = None
lowest_possible = 3 * 9 * 9 + 1
for i in range(9):
for j in range(9):
if hints[i, j] == 0:
base_x = (i // 3) * 3
base_y = (j // 3) * 3
total_possible = np.sum(possible[i, :, :])
total_possible += np.sum(possible[:, j, :])
total_possible += np.sum(possible[base_x:base_x+3, base_y:base_y+3, :])
if total_possible < lowest_possible:
lowest_possible = total_possible
best_location = (i, j)
(i, j) = best_location
values = np.arange(10)[possible[i, j, :] == 1]
return i, j, values[0]
If we change the total_possible calculation to simply total_possible = np.sum(possible[i, j, :]) (which just picks the cell with the fewest possibilities), then it actually runs slightly slower at about 2.1 seconds.
If your approach was very quite similar to mine, then I think these tricks make quite a big difference simply because it increases value of the random guess and makes it quicker for subsequent logical elimination to either find a solution or contradiction, which helps to avoid wasting more time with further guessing (and branching).
However, I think that further optimizations of this basic approach might just be chasing diminishing returns. Knuth’s algorithm X, which can be applied to Sudoku and solve all 50 puzzles in about 1/3 of a second, seems like a much more elegant and efficient solution.
1 Like
Road to level 15
Since this thread got a few people interested in solving the first 100 problems, I got a bit of inspiration to continue where I left off a few months ago. Recently, I reached 350 (level 14), but I’m right now 21 problems away from the next goal.
At this point, I’ve ran out of 5%-difficulty problems to solve. So, I’m outsourcing the question: which one should I solve next?
- P211 Divisor Square Sum (difficulty 50%)
This is the next problem in numeric order. - P743 Window into a Matrix (difficulty 10%)
The last remaining problem of 10% difficulty. - P709 Even Stevens (difficulty 15%)
The last remaining problem of 15% difficulty. - P300 Protein folding (difficulty 50%)
One of the 3 problems I need for the Triangle Trophy. - P754 Product of Gauss Factorials (difficulty 20%)
Nothing special, just seems interesting. - P752 Powers of 1 + √ 7 (difficulty 25%)
I just like surds.
0
voters
Note: From experience, difficulty ratings can be subjective. There’s a reason I’ve not solved P743 or P709 yet.
1 Like
You know which should go next for you @yebellz
I am working on P211 in case you want to join me. I can solve it in 50 min in a brute-force way and am looking for a more efficient approach.
Anyone doing Advent of Code this year?
2 Likes
Is this a race kind of event? I code veeeery veeeery slowly.
2 Likes
Meh yeah technically the leaderboards are time-based, but I’m also a slow coder so not expecting to land on any leaderboards 
Okay, I did one. Started out in Ruby, but that makes everything too easy so maybe once I catch up I’ll switch over to my new favorite language, MicroPython, to make it a challenge.
I’ll be slow, too, but we can have our own private OGS leaderboard! In fact, I just made it.
You can join with code 2516370-4dd8a512.
1 Like