Another brain teaser from my muddled mind

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
User avatar
Johnny Canuck
Kiloposter
Posts: 1647
Joined: Sun Oct 03, 2010 10:44 pm
Location: Montréal 😃, Québec 😕, Canada 😃

Another brain teaser from my muddled mind

Post by Johnny Canuck »

(...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.
I'm not dead yet. In a rut right now because of stress from work. I'll be back later in S89. I also plan to bring back the Mastergram - if I can find a way to run a timer or clock through pure MediaWiki without having to upload to Vimeo every time.
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Re: Another brain teaser from my muddled mind

Post by Gavin Chipper »

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.
Last edited by Gavin Chipper on Wed Dec 02, 2020 12:06 pm, edited 4 times in total.
User avatar
Thomas Carey
Kiloposter
Posts: 1478
Joined: Sun Jan 09, 2011 4:17 pm
Location: North-West of Bradford
Contact:

Re: Another brain teaser from my muddled mind

Post by Thomas Carey »

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
cheers maus
User avatar
Thomas Carey
Kiloposter
Posts: 1478
Joined: Sun Jan 09, 2011 4:17 pm
Location: North-West of Bradford
Contact:

Re: Another brain teaser from my muddled mind

Post by Thomas Carey »

gevin where's your 19
cheers maus
User avatar
Thomas Carey
Kiloposter
Posts: 1478
Joined: Sun Jan 09, 2011 4:17 pm
Location: North-West of Bradford
Contact:

Re: Another brain teaser from my muddled mind

Post by Thomas Carey »

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
cheers maus
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Re: Another brain teaser from my muddled mind

Post by Gavin Chipper »

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.
Fiona T
Kiloposter
Posts: 1447
Joined: Mon Mar 18, 2019 12:54 pm

Re: Another brain teaser from my muddled mind

Post by Fiona T »

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)
Last edited by Fiona T on Wed Dec 02, 2020 11:14 am, edited 1 time in total.
User avatar
Thomas Carey
Kiloposter
Posts: 1478
Joined: Sun Jan 09, 2011 4:17 pm
Location: North-West of Bradford
Contact:

Re: Another brain teaser from my muddled mind

Post by Thomas Carey »

fiona where's your 13
cheers maus
Fiona T
Kiloposter
Posts: 1447
Joined: Mon Mar 18, 2019 12:54 pm

Re: Another brain teaser from my muddled mind

Post by Fiona T »

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
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Re: Another brain teaser from my muddled mind

Post by Gavin Chipper »

Thomas Carey wrote: Wed Dec 02, 2020 10:26 am gevin where's your 19
Check mine now.
User avatar
Thomas Carey
Kiloposter
Posts: 1478
Joined: Sun Jan 09, 2011 4:17 pm
Location: North-West of Bradford
Contact:

Re: Another brain teaser from my muddled mind

Post by Thomas Carey »

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
cheers maus
Paul Anderson
Enthusiast
Posts: 300
Joined: Tue Dec 10, 2019 2:18 pm

Re: Another brain teaser from my muddled mind

Post by Paul Anderson »

what's with the coloured text? Illegible really
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Re: Another brain teaser from my muddled mind

Post by Gavin Chipper »

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!
Fiona T
Kiloposter
Posts: 1447
Joined: Mon Mar 18, 2019 12:54 pm

Re: Another brain teaser from my muddled mind

Post by Fiona T »

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

https://www.phpbb.com/customise/db/exte ... er_bbcode/
User avatar
Johnny Canuck
Kiloposter
Posts: 1647
Joined: Sun Oct 03, 2010 10:44 pm
Location: Montréal 😃, Québec 😕, Canada 😃

Re: Another brain teaser from my muddled mind

Post by Johnny Canuck »

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.
I'm not dead yet. In a rut right now because of stress from work. I'll be back later in S89. I also plan to bring back the Mastergram - if I can find a way to run a timer or clock through pure MediaWiki without having to upload to Vimeo every time.
Post Reply