c4countdown

(...and maybe not even just my own... I think I recall a puzzle similar to this on here before.)

What is the smallest, positive, natural number that contains every prime below 100 in it as a substring? If a prime is two digits, it must appear as a single block, with no digits in between.

In a day or two I'll post my best effort along with a vague explanation of how I got it.

Interesting puzzle. I have:

231129413434715359616737838979

My thinking was that the best you could possibly do is start with a 2 and have as few "dead ends" as possible. All the even numbers (other than the initial 2) will involve a dead end as well as the 5. Starting with a 2, you get 23 free of charge. But as you have 29, 41, 43, 47, 53, 59, 61, 67, 83, 89 that's at least 10 digits in the sequence that will be a "dead end". And if you can keep it to exactly 10, then perfect.

So basically, starting with the 2, put the lowest number you can next that won't give you a dead end that you haven't already accounted for and hopefully you get through all the numbers. If not, go back to the latest point in the sequence you can and redo from there. It seemed to fall out quite nicely when I tried it. If I did it right.

Edit - I think 1123129413434715359616737838979 works better because even though two 2s are dead ends, it's still the same number of digits.

Edit 2 - I think I missed out 17 and 19. (Edit 3 - Stick them at the end for now.)

Edit 4 - Well I've fudged them in to get 112312941343471735375961967838979.

Edit 5 - Actually it seems that I added a digit by making it start with a 1, so go with 23112941343471735375961967838979. This looks to be a smaller number than Carey's so if it's right, it's better. But given that we're in edit 5, don't hold your breath.

ok so i'm sure you know about the haruhi problem but i haven't looked into it enough to really have any idea how to go about this other than brute force so - here goes.

obviously 2 3 5 7 are contained in longer boys so we can ignore them, and now it's basically try and get a string of digits where as many of the blocks of 2 numbers as possible are consecutive primes, ya know, have as little redundancy as possible. once you've got the least digits you can fart around getting the smallest one to the front.

so. 23 29 41 43 47 53 59 61 67 83 89 (11 total) start with one of them digits what no 2 digit prime ends in, whereas the other guys (11 13 17 19 31 37 71 73 79 97, 10 total) don't got that. i assume it's fairly easy to get 11 strings, each starting with one of the first set and then having some number of the others chained at the end. 23 is the smallest starting set of 2 digits, so i wanna start with that, ram as many ones as possible there and end when you got a thing higher than the 2 from 29. so that looks to me like it should be 23113 - 23 and 11 all prime, and at every point i'm taking the next smallest digit. ok cool so then you start with 29, you can go 29 (cause the next starting numbers start with a 4) and then you can actually kill it here cause it seems to me that putting the 7 next (the only 90s prime is 97, like and share if you're a true 90s kid) would create a bigger number than just ending that chain and starting the next one at 41. so let's go. but actually since we've had 11 already you can then put in the 3 to get 13, and, the 4 from 43 is less than the 7 from 37 so kill that there. we've done 3/11 chains now and got 231129413.

new paragraph. next up is 43, but we've had 31, and 37 gets you a bigger number than just leaving it at 47. ok so let's go 47, finally a longer chain emerges cause you can stick on a 1 for 71 and then another 7 for 17 before you then have a number bigger than 53. so that chain is 4717. thence, you do 53 - but 31 gone and 37 too big, end chain. then 59 but again 97 too big so end. so far we have 2311294134347175359.

into the sixties, john lennon uta. 61 first however the only teen that's not gone is 19 which is too big, so we move on to 67, and we can bang on a 3 for 73 here. and actually since the next chain starter is 83 now it's finally time to deploy yon 37, so we tack a 7 onto the end, but then the only remaining 70s kid is 79 and the 9 is still too big, so 6737 is where that chain ends. 83 up to bat and we've run out of thirties so that's that. now 89 - and we have an interesting dilemma that i hadn't really thought of. obviously we can staple the 7 on for 97 and fire back with a 9 for 79, getting a chain of 8979. but, we've run out of starting chains and haven't dealt with 19, so i think the best option here is staple the nine onto the end of the last 1 we had at teh end of summat, and that would be the 61. so in total my eleven chains look like

2311 29 413 43 4717 53 59 619 6737 83 8979

and indeed all of the two digit primes appear exactly once in one of those chains. and now we just tape em together, 23112941343471753596196737838979 final answer

gevin where's your 19

but yeah good point by gev at the end, reworking my answer hang on

edit: actually i don't think he does i worked out that you essentially need one digit for each of the primes that start with 1 3 7 9, and 2 digits for the ones that don't - so 2x11+10=32 digits, and if i were to pull some shit like starting with 1, i would have to add in extra digits, because i am starting new chains, and thus my number would be bigger. so i'm sticking with what i said

Thomas Carey wrote: ↑Wed Dec 02, 2020 10:30 am but yeah good point by gev at the end, reworking my answer hang on

edit: actually i don't think he does i worked out that you essentially need one digit for each of the primes that start with 1 3 7 9, and 2 digits for the ones that don't - so 2x11+10=32 digits, and if i were to pull some shit like starting with 1, i would have to add in extra digits, because i am starting new chains, and thus my number would be bigger. so i'm sticking with what i said

It seems I accidentally added an extra digit to start with a 1 without noticing. Mine is a complete train wreck now anyway.

2311719737929414347535961678389 as a first attempt

it's littler than Maus and Gev's so will call that a win


(edit to remove extra typo digit)

fiona where's your 13

Thomas Carey wrote: ↑Wed Dec 02, 2020 11:13 am fiona where's your 13

Ah balls

My list of primes below 100 didn't include 13

Thomas Carey wrote: ↑Wed Dec 02, 2020 10:26 am gevin where's your 19

Check mine now.

ok, yeah, i feel like i should hvae hit yours with my method but i probably rushed it at that point - i hadn't used up the 73 by that point, so i should have stuck the 3 in next. either way i think that's it

what's with the coloured text? Illegible really

Paul Anderson wrote: ↑Wed Dec 02, 2020 1:59 pm what's with the coloured text? Illegible really

Highlight it. It's to stop accidental spoilers for people trying it themselves!

[spoiler]There is a spoiler extension but we don't appear to have it.[/spoiler]

https://www.phpbb.com/customise/db/exte ... er_bbcode/

Well, I'll be danged! When I attempted this puzzle I started my string with 411317197379..., thinking having all of the {1,3,7,9} primes in a single chain would save me one digit that couldn't be made up elsewhere. Which I now see is BS. Congratulations Gevin, it seems like edit #5 takes it for now, and you were right not to fall for the trap of starting with a 1, but will leave the puzzle up while I and any other interested takers see if it can be bettered!

EDIT: Yep, will need a new algorithm. That 17 and 19 aren't cooperating with me.

EDIT 2 (20 December): Did it again, blindly, by using Maus' approach of starting with eleven "chains" beginning with the non-reusable digits, and got the same answer as Gevin's Edit #5. Looks like that's the official winner.