The Sphinx's Lair

@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

Gareth McCaughan

If you have a reasonably fast sudoku solver then you have a sudoku generator, almost

boboquack

@Wen1now It generates a random sudoku every time you reload the page.

micsthepick

12:15 AM

@Wen1now Mine works in a similar fashion.

Gareth McCaughan

(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)

Wen1now

@boboquack Not for me.. it's still the same sudoku

micsthepick

@micsthepick projecteuler.net/problem=96

Gareth McCaughan

@Wen1now I think you should follow the link on the word "random"

Wen1now

Now, if it had linked an xkcd comic then I wouldn't've had to follow the link...

boboquack

12:19 AM

@Wen1now It's a random sudoku, do you get the point?

Wen1now

For some reason I'd remembered that comic as 222. Oh well, one off isn't that bad

What's the time?

micsthepick

11:22 here

Can't you just look at the top/bottom right of your monitor? :P

Gareth McCaughan

01:23:45 about 5 seconds ago here.

Wen1now

What is the smallest prime that cannot be expressed as (pq+1)/(p+q) for p,q prime?

For example 2 doesn't count since p=3,q=5 gives (3*5+1)/(3+5)=2

micsthepick

just checking, it's not 3 is it?

Wen1now

12:29 AM

p=5,q=7

Gareth McCaughan

do you know that there is any prime that can't be so expressed?

Mike Q

Optimus Prime, Prime rib, Prime directive

Eric Tressler

for all logic puzzles I know of, a solver with a metric is all you need for a generator

Wen1now

@GarethMcCaughan I think so

I haven't checked by hand though so I might be stupid

Gareth McCaughan

well, the smallest that isn't so expressible with p,q < 100 seems to be 19

this seems like a question that's either really easy or really hard

Wen1now

12:34 AM

@micsthepick Now I so want to do some project Euler questions...

Gareth McCaughan

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

maybe

micsthepick

@Wen1now have you done 96 yet?

It should be easy enough if you already have a working solver

Wen1now

p=23, q=109

Gareth McCaughan

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.

micsthepick

can't be any of these: 2 3 5 7 11 13 19 17 23 29 31 37 41 53 43 47 59 61 71 67 89 79 113 103 127 109 139 149 151 167 163 181 199

Rubio

12:38 AM

I'm not finding one for 73

micsthepick

yeah ^

Rubio

at least not for any prime in the first 10,000 primes

Wen1now

yeah 73 was the answer

Gareth McCaughan

it's not hard to verify that 73 does it

micsthepick

I only checked the first 100 primes

Gareth McCaughan

12:39 AM

but proving that nothing smaller does seems really painful

Rubio

3, 5, 2
5, 7, 3
7, 17, 5
11, 19, 7
13, 71, 11
19, 41, 13
29, 41, 17
23, 109, 19
31, 89, 23
31, 449, 29
37, 191, 31
41, 379, 37
43, 881, 41
71, 109, 43
71, 139, 47
59, 521, 53
71, 349, 59
71, 433, 61
89, 271, 67
73, 2591, 71

huzzah computers.

(those are p, q, prime triplets)

107 and 131 also have no solutions in the first 10k primes

Wen1now

Wait are you going (p,q) -> prime OR prime -> (p,q)?

Gareth McCaughan

has to be the former, if I'm understanding the question right, not only because he said so but because otherwise 5,7,3 doesn't work

Rubio

my listing is p,q, prime. so p=3 q=5 give (pq+1)/(p+q) of 2.

Gareth McCaughan

(I don't expect any of the others work either the wrong way around, except maybe by coincidence, but that was the only one I bothered checking)

micsthepick

12:44 AM

how do you prove that 107 cannot be done?

Gareth McCaughan

find 107^2-1. factorize. try shifting all pairs of factors down by 107 and see that none of them yields two primes.

Wen1now

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?

Rubio

I'm just brute-forcing the search space with the first 10k primes - it's big but not absurdly big, so it doesn't take that long

micsthepick

@Rubio you mean by generating prime pairs?

Rubio

cuz I'm not as mathsy as Gareth, but I can write perl code pretty quickly :)

Gareth McCaughan

12:46 AM

for each prime p: for each prime q: compute (pq+1)/(p+q); if an integer, record it. When done, go through small primes and report what was found.

Rubio

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. :)

micsthepick

now find the first such prime that is a palindrome, ;)

131

11, actually :)

eh? 11 was doable

12:48 AM

oh. the first non-match? yeah 131

micsthepick

duh

Gareth McCaughan

if you mean the first match, that would be 2, not 11

boboquack

Hi @Doorknob!

Rubio

@GarethMcCaughan Pah. trivial palindromes are boring.

:)

Mike Q

what about 107 with bad handwriting?

Sp3000

12:49 AM

71 has a lot of low solutions: (79, 701), (83, 491), (101, 239), (107, 211), (113, 191) e.g. -- I just find that slightly amusing

Gareth McCaughan

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

boboquack

what about 73 in unary?

Gareth McCaughan

oh no wait

Wen1now

What are we waiting for?

Gareth McCaughan

about log log r prime factors, about log r factors

but that still isn't enough to make it usually work

Wen1now

12:51 AM

Hmm... my program, I think, agrees with you there

Gareth McCaughan

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

micsthepick

Find the first prime that follows that rule and contains a pandigital string (digits 1-9 together)

Wen1now

Pandigital string?

Gareth McCaughan

er, of course I mean each has probability 1/log r of being prime after adding r (I said subtracting before, I think, but that was wrong)

Wen1now

Does that include 0?

Gareth McCaughan

12:53 AM

@micsthepick I conjecture that none exist.

Wen1now

@GarethMcCaughan Didn't you just say that most large primes work?

micsthepick

no, it does not include 0

Gareth McCaughan

no, I said that most large primes don't work

if you have evidence that most large primes do work then I have probably goofed somewhere in my handwavy argument above

Wen1now

Okay okay, I think I see the confusion

I say 'work' = cannot be represented

Gareth McCaughan

ah, oops

Sphinx

12:55 AM

0

Q: Your mission is to break this mastermind code

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...

logical-deduction

Wen1now

So many mastermind questions... I might try writing a script that solves mastermind problems

Gareth McCaughan

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

Wen1now

> pandigital string (digits 1-9 together)

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

Gareth McCaughan

10123465789^2-1 (from the second-smallest pandigital prime) seems not to have too many factors. It might possibly work.

(i.e., 10123465789 may turn out not to be representable)

micsthepick

but would it be the first case

Gareth McCaughan

1:01 AM

the only smaller pandigital prime has a lot more factors and I wouldn't be so optimistic about that one

Wen1now

It works

Gareth McCaughan

works in which sense?

Wen1now

wait nvm

I inputted the wrong thing

I'll just let my program have a chance to run...

Okay I may need to efficientise my algorithms

micsthepick

10 hours later...

Wen1now

For primes ~10000000 it takes a few seconds

micsthepick

1:07 AM

no

it has to be 2^x not x^2, derp

Wen1now

Okay I think it's my factor generation algorithm that slows it down

Sp3000

btw Gareth re:C4 yesterday, how does opposition -> CON? (is it as in "pros and cons", or...?)

Gareth McCaughan

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.

Wen1now

Is there any easyish way to find all factors of a number?

Wait that's NP-complete right?

Gareth McCaughan

not known NP-complete

probably not NP-complete

but also not known polynomial time

Sp3000

1:11 AM

(Ah k, just checking it didn't have some definition I hadn't heard of :P)

Also I'd recommend using a library than rolling your own factoring for efficiency, unless it's for learning how to write a factoring algorithm

Gareth McCaughan

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

boboquack

Quote Wikipedia:

Gareth McCaughan

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

boboquack

Unsolved problem in computer science:

Gareth McCaughan

for numbers of more reasonable size, other simpler algorithms are usually preferred

boboquack

1:13 AM

Can integer factorization be done in polynomial time?

Gareth McCaughan

but nothing is super-fast once the numbers get fairly large

boboquack

(more unsolved problems in computer science)

Wen1now

It's not exactly factorisation, but rather finding all factors

Gareth McCaughan

the best way to find all factors is to factorize first and use that

unless your number is small and has outrageously many factors, like 60

boboquack

The best time according to wikipedia is (bear with me while I mathjax this up):

Sp3000

1:14 AM

(Nothing super-fast... yet. Something something Shor's algorithm? Or have I misunderstood the effectiveness of that one)

Gareth McCaughan

well, OK, if you have a quantum computer of sufficient size then you can use Shor's algorithm and it's pretty quick

Wen1now

@GarethMcCaughan p^2-1 generally has a lot of factors right?

Gareth McCaughan

but no one (so far as we know) is close to having such a thing

p^2-1 is always a multiple of 24

and of course factors as (p+1)(p-1)

but neither of those is obliged to have a lot of small factors

Wen1now

Good point, I should probably be doing this on my qpc

boboquack

oops

micsthepick

1:16 AM

@GarethMcCaughan p = 0 is a counterexample :P

boboquack

let's try that again

Gareth McCaughan

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

micsthepick

so p must be prime for that to work?

Gareth McCaughan

but any prime other than 2,3 -- indeed, anything that isn't a multiple of 2 or 3 -- has the property that r^2-1 is a multiple of 24

Sp3000

Wen are you using Python?

Gareth McCaughan

1:17 AM

(8 because odd numbers squared are 1 mod 8; 3 because nonmultiples-of-3 squared are 1 mod 3)

@boboquack I do not believe your formula as it currently stands

though perhaps it is an anagram of the correct formula

Wen1now

By definition of O I don't think the constant terms out the front are necessary

Gareth McCaughan

or perhaps some exponents have moved to the wrong place

Wen1now

@Sp3000 Yeah I'm pythoning

Gareth McCaughan

I think some of those constant terms are meant to be exponents

boboquack

no, that didn't quite work

Sp3000

1:18 AM

@Wen1now Try pip install'ing sympy and in code import sympy.ntheory.factorint or something maybe?

Gareth McCaughan

anyway, the formula is basically what I said: constant times log(n)^1/3 times log(log(n))^2/3

boboquack

Gareth McCaughan

nope, still messed up @boboquack

Wen1now

Still got constant terms

boboquack

there we go

micsthepick

1:20 AM

@Wen1now still still

Gareth McCaughan

unless it's displaying differently for me and for boboquack, it's still all wrong

but if you square the log log n factor then I think it might be right

Wen1now

@GarethMcCaughan 'Math formula anagramming class': try anagramming 'T(n+1)/2=n_n

Gareth McCaughan

that would be fun: progress to more and more intricate and obscure formulae

boboquack

^screenshot

Gareth McCaughan

might be a good way of developing students' intuition

@boboquack yeah, that's right, where b = log n

Wen1now

1:21 AM

Hey. Nobody has solved my formula yet :(

boboquack

where b=number of bits in n, so roughly log n

Gareth McCaughan

@Wen1now of course they have, it was just too obvious to bother stating explicitly

boboquack

oh whoops, missed out ^2

Wen1now

Okay harder question comming up

boboquack

I give up

Sp3000

1:23 AM

_T(n)=1/n+2n

VTC too broad

boboquack

T_n=n(n+1)/2

@Sp3000 I think it has to be the correct formula

Wen1now

For n sufficiently large, anagram this to give a commonly known sequence undo(rn^hip)

What I mean of course is n=k,k+1,k+2,k+3... this gives a sequence for some k

Gareth McCaughan

so, anyway, the first pandigital prime in base 10, namely 10123457689, is in fact irrepresentible

so is the second

but the third, 10123465897, has two representations: (11909959879, 67489772641), (67489772641, 11909959879)

@Wen1now yeah, that one is phamous too

Wen1now

How did you get that so fast?

Gareth McCaughan

the hip was a giveaway

or do you mean the representations?

Wen1now

1:27 AM

I mean the representations

Gareth McCaughan

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

boboquack

@Wen1now you like big numbers, here is a question for you:

17

Q: Golf a number bigger than TREE(3)

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...

code-golf math number busy-beaver

micsthepick

is there a 1-9 pandigital prime that comes before though?

Gareth McCaughan

@micsthepick oh, I don't know

micsthepick

the OIES sequence appears to include the 0

Gareth McCaughan

1:31 AM

no, wait, I do know

oh, no, wait, I don't know

give me a minute, though

1123465789 False
1123465879 False
1123468597 True
1123469587 False
1123478659 False
1123485967 True

False means not representable, True means representable

so once again we get lucky and the first pandigital prime is not representable

micsthepick

or are we lucky?

Gareth McCaughan

for digits in itertools.permutations('1123456789'):
p = int(''.join(digits))
if sympy.ntheory.isprime(p):
print(p, len(list(reps(p)))>0)

micsthepick

just indent before copying

Gareth McCaughan

what do you mean by "indent before copying"?

oh, I see

you mean indent for Markdown rather than indent for Python

micsthepick

use ctrl/command ] then copy

Gareth McCaughan

1:37 AM

does that actually work, though? I know that Markdown mostly doesn't work in multiline chat comments

for digits in itertools.permutations('1123456789'):
   p = int(''.join(digits))
   if sympy.ntheory.isprime(p):
     print(p, len(list(reps(p)))>0)

that was all indented by two spaces. do I need more, or does it just not work?

ah, four spaces is enough

boboquack

golf tip: if sympy.ntheory.isprime(p):print(p,len(list(reps(p)))>0)

Gareth McCaughan

I wasn't golfing

Sp3000

... we're not golfing here :/

boboquack

I can see that

Gareth McCaughan

(why the hell would I be golfing?)

Wen1now

1:39 AM

Why do we have a 1 at the front?

boboquack

It also saves time while writing code, because you don't have to worry about indentation

Gareth McCaughan

because 1+2+...+9 is a multiple of 9

boboquack

what about something like 1234567289?

Gareth McCaughan

bigger than 11...

(if we really needed all the pandigital numbers then of course we'd need to include those too)

boboquack

oh, there is a 10-digit pandigital prime which starts with 11?

Wen1now

1:40 AM

I am actually so dumb...

Sp3000

(Golfed code is much less readable, so even in quick hack scripts it may be useful to actually have proper indentation)

Gareth McCaughan

@boboquack if you define "pandigital" as @micsthepick did above to permit having no zeros

Wen1now

Hmm

boboquack

ok, it's killing me, what is this prime?

micsthepick

7 mins ago, by Gareth McCaughan

1123465789 False
1123465879 False
1123468597 True
1123469587 False
1123478659 False
1123485967 True

Gareth McCaughan

1:42 AM

first one is 1123465789

Wen1now

pie=0+i^1

micsthepick

all of them are prime

Wen1now

Might be a bit easy to some of us

boboquack

e^ipi+1=0

micsthepick

no

Gareth McCaughan

1:42 AM

@Wen1now Any time you feel that way, just remember the story of the Grothendieck prime.

micsthepick

e^(i*pi)

Wen1now

2^a^b^c=2+2

Sorry I'm just stalling for time

micsthepick

not possible for integers

Gareth McCaughan

@micsthepick you do realise it's an anagram?

though I can't help thinking there might be a missing +

Wen1now

There we go, it's also solvable in integers now

Gareth McCaughan

1:46 AM

ah, there is no longer a missing +

micsthepick

2,1,1

Wen1now

Interesting number: \sqrt(v)+c^2^2-1/1

I hope that's correct...

Hey, somebody else make some. I want to give these a shot as well

Gareth McCaughan

I'm trying to work out your latest, which is the first one that wasn't obvious :-)

oh, I see

no, wait, maybe I don't see

yeah, I do

Wen1now

It's not really a formula (no =) but it gives an interesting number

boboquack

Dubious: .1+.2/1.3=-1+2

Wen1now

1:50 AM

I think I see

Gareth McCaughan

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 :-)

boboquack

@Wen1now see mine?

Wen1now

Try this one (for n staying natural)

@boboquack yep

Gareth McCaughan

@Wen1now were you actually going to post "this one"? :-)

Wen1now

No...

I'm still working on ti

{} means fractional part btw

micsthepick