@micsthepick I made one just for the fun of it :) It brute-forces the sudoku, efficiently compared to stupid brute-force but inefficiently compared to clever brute-force
(fill in a grid, then repeatedly remove numbers until you can no longer do so without rendering the sudoku unsolvable; for extra points, at that point try adding and removing numbers and explore to see if you can reduce the number of clues required)
I mean, if there isn't a trivial obstruction then it'll be some Goldbach-like thing that boils down to whether there are monstrous coincidences in the structure of the primes
so (pq+1)/(p+q)=r is the same as (p-r)(q-r) = r^2-1 i.e. we're looking for a factorization of r^2-1 such that shifting both factors by r yields primes. so a place to look (if indeed there are prime r for which this doesn't work) would be r for which r^2-1 doesn't have too many factors.
What I mean is, are you generating all possible (p,q) and finding the value (pq+1)/(p+q) or are you choosing a prime and testing it against (p,q) values?
If anyone cares, up to 223 all primes can be decomposed into p,q where each p,q are within the first 10k primes, except: 73, 107, 131, 157, 173, 179, and 193.
I'm now reducing my contributions to global warming by stopping my script. :)
so if r is a large prime then r^2-1 has about log log r factors, typically of size about r, and each has probability 1/log r of being prime. so I expect most big primes can't be represented in this way
obviously r^2-1 always has a bunch of small factors so for smaller r taking d(r)=log r is typically a substantial underestimate, which is handwavily why most small primes seem to work
Here is an altered mastermind puzzle which instead of colored pegs I used digits from 1 to 9 without any repetition. The picture below shows four guesses and their corresponding scores.The black pegs are for every correct digit and correct position and the white pegs are only for the correct digi...
so let's be a bit more careful about @micsthepick's question. If r is a large enough prime then r^2-1 can be split into two factors in about log r ways (on average, and the distinction between "on average" and "almost always" may make the argument I'm making rubbish, but never mind) and each has probability about 1/(log r)^2 of working. So a given prime r is representable with probability about 1/log r.
so actually
there are probably enough pandigital primes for plenty of them to be representable
e.g. I guess most length-20 primes are pandigital, and there are zillions of them, and 1/log(10^20) is pretty big so plenty of them will be representable
Doesn't that mean that the digits must be together? I'm sure your argument still works, but you'll probably need to take like 10000 digit primes or something
Well, 10000 digit primes for most of them to be pandigital
I think that second pandigital prime is irrepresentible
@Sp3000 yes, I was thinking pros and cons. It isn't exactly great, as I think I said at the time, and my guess is that CON is not in fact what "opposition" indicates.
there are algorithms that take time that looks like n^f(n) where f(n) is some ridiculous thing like log(n)^1/3 log(log(n))^2/3. Something like that, anyway
actually applying the most efficient such algorithms to large numbers involves really big linear-algebra operations and stuff and tends to be done on large networks of fast computers
none the less, for numbers of that form you might prefer something like the elliptic curve method that gives answers quicker when the factors are smaller
@micsthepick 0 is not prime
however, I should have excluded 2 and 3 as well
since they are primes and actual counterexamples to what I said
def reps(p):
t = p*p-1
for d in sympy.ntheory.divisors(t, generator=True):
e = t//d
u,v = d+p,e+p
if sympy.ntheory.isprime(u) and sympy.ntheory.isprime(v): yield (u,v)
obviously the indentation is screwed [EDITED: not any more]
and then I just pasted in the list of the first few pandigital primes from OEIS
incidentally, I question just how well known the Lucas sequence really is
The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti has at most i vertices, and no tree is a minor of any tree following it in the sequence.
TREE(1) = 1, with e.g. T1 = (1).
TREE(2) = 3: e.g. T1 = (1...
yeah, I was a bit put off by "interesting number" because I was trying to find a way to make it actually give a single number rather than something depending on a parameter :-)