MPMSolution: The Marching Band Problem

[@laremere]

The more Matt ensured that there wouldn't be any band music, the more I knew there would be.

[@deannaj4265]

Guilty 🙋🏼‍♀️

[@connorwhitworth3172]

“MORE BAND MORE BAND” is my favourite series Matt has ever done.

[@secondengineer9814]

I wrote Python for this one but my brother found a good way to figure it out in his head. He realized that if all numbers 1,2,...n are included in a factorization of a number (let's say k) then k * n+1 is the lowest number that has 2n factors. 64 is 2^6, so you just need to double the number of factors 6 times starting from 1 (1 factor). The steps are as follows: 1 (1 factor) * 2 2 (2 factors) * 3 6 (4 factors) * 4 24 (8 factors) * 5 120 (16 factors) * 7 (6 is already a factor!) 840 (32 factors) * 9 (8 is already a factor!) 7560 (64 factors) This method gives you the optimal prime factorization by giving you a pattern to add new prime factors in (in this case, 2, 3, 2^2, 5, 7, 3^2).

[@Ultiminati]

that's a pretty practical way

[@thumper8684]

That is same same method I used, but you explanation is clearer than mine. I took the list of primes and squares of other numbers on the list (including squares of squares etcetera). It looks like you did the same thing in practice but you framed it better than I ever could.

[@TheCrewdy]

This is very good. I got to the answer but I wasn't able to definitely rule out a smaller number.

[@carlschmittbiel6805]

I just looked it up in a numberphile video about "antiprimes"

[@SoleaGalilei]

That's how I got the answer too. Having seen it, I knew I just had to check the list of highly composite numbers. Without that video I wouldn't have known what they were called!

[@diarya5573]

I'm exactly at position 512 and will be putting all my efforts in to keep it that way. Also, petition to make band music the rick roll of standupmaths.

[@Fepe55]

Hey, I'm 508, hello close neighbour!

[@hamiltonianpathondodecahed5236]

Take my sign and don't give him such ideasಠ_ಠ

[@diarya5573]

@@Fepe55 Hello :)

[@diarya5573]

@@hamiltonianpathondodecahed5236 :)

[@LincolnChamberlin]

As long as he makes it quite enough so everyone can hear, that are just put subtitles so you don't need to hear

[@haalstra]

I was disapointed when Matt said there whouldn't be any music... Thanks Deanna :D

[@deannaj4265]

#moreband

[@jonathanlevy9635]

Yeah! I'm in the hall of fame of people who were mentioned in Matt's videos. I am so proud of myself

[@Lioness99a]

Thanks for the honourable mention! So far I think that Excel is winning but it's a fun competition - certainly gets the old brain cells moving

[@TheyCallMePhinq]

yeah I just googled "most divisible numbers' and that's how I got the answer...

[@n00dle_king]

Ugh I noticed the part about reversed numbers like (1,8) and (8,1) counting twice but forgot that it takes a pair to count twice so I ended up looking for the smallest number with thirty two divisors.

[@CR0SBO]

Surprise Band Music! That's my second favourite kind of Band Music, and it's very close behind More Band Music, which is the all time best kind.

[@wafelsen]

The first two of these highly composite numbers being between two primes makes a degree of sense. You already know that numbers one more and one less will not be divisible by any of the primes that divide the highly composite number. So it is at least more likely that they will be prime.

[@Matiburon04]

This one was the first one I gave it a go. Got the wrong answer because I assumed the number with the smallest amount of prime factors was going to be the smallest in size. But still got a valid answer! had a lot of fun. Thanks for making these.

[@hamiltonianpathondodecahed5236]

Today is Independence day in India , and listening to band music just feels normal (＾3＾♪ (＾3＾♪

[@davidalearmonth]

I liked the marching band music. But I did find it much easier to focus when you turned down the volume.

[@unperrier5998]

The smallest (I think) Python: from itertools import count for x in count(1): if sum([1 for y in range(1, x+1) if x % y == 0]) == 64: print("Solution:", x) break Which I sent by email but hasn't been picked to apepar in the video... but visual basic was :(

[@murphygreen8484]

Can confirm, this does work and is super slick

[@murphygreen8484]

How does your sum work?

[@JoshBlasy]

i had a separate comment, then saw yours, but you can do it in one line: [i for i in range(10000) if len([j for j in range(1,i+1) if i%j==0])==64][0]

[@RG001100]

using a generator rather than list comprehension: next(i for i in xrange(10000) if len([j for j in range(1,i+1) if i%j==0])==64)

[@sergey1519]

basically don't mess with code golfers.

[@R.a.t.t.y]

We can choose depending on our bandwidth.

[@R.a.t.t.y]

We need an August band. A March band is months old.

[@sudhenduahir802]

More Band More Band made my day. Matt was told by Deanna.. and it was awesome..

[@bnoel12345]

At 14:29 I think James Crewdson was on to something about the answer being between two primes. It doesn't specifically have to do with numbers that have 64 divisors, but rather it has to do with the minimal solutions for this kind of puzzle. I sent in my email submission late, so Matt probably didn't get to see it before making the solutions video, but when I found the minimal number that has n divisors for n from 1 to 64, I found that 24.3% of those numbers were sandwiched between twin primes, and 70.3% were adjacent to at least one prime. For random numbers between 1 and 7560, only about 2% are between twin primes and only about 23% were adjacent to any primes. However, highly composite numbers seem to have the best track record for finding primes. For the first 20 highly composite numbers up to 7560, fully 35% of them are sandwiched between twin primes, and an an amazing 90% of them are adjacent to at least one prime.

[@rmsgrey]

That's not a very surprising result - in general, these numbers will have lots of prime factors, and the numbers either side won't be divisible by any of those primes, meaning there are fewer primes those neighbours could be divisible by, and more chance of not being divisible by any.

[@TheCrewdy]

@@rmsgrey @bnoel12345 Good explanations both. I'm not a maths person and only noticed the prime thing because I was wondering if the answer was 7559 - another Parker "negative deposit" answer - because I don't need to recruit myself so I only need 7559 to get to 7560.

[@IndustrialQueue]

I built out a spreadsheet that figured how many factors a specific number has. It helped learn the scaling of divisors as prime factors change. It was pretty fascinating to see how scaling a number by a specific factor increments the number of factors by a set amount.

[@dagordon1]

Thanks, Matt and Deanna, although I could have done without seeing tOSU band in the lower right corner - Go Blue!

[@nodroGnotlrahC]

Deanna Judd is now officially my second favourite Deanna.

[@L4Vo5]

I did it with normal brute force code, then went back and rewrote my code to use the prime factor multiplications and a trick where for every new number X I tested, I only found the first prime factor P, divided it by it to get N, looked at what N's prime factors had been (for which I had to save all the numbers' prime factors), and made X inherit those, plus adding 1 to the P exponent. This made it much faster, at the cost of potentially using way too much memory if I tried to go big. I wanted to see if there was a way to figure it out directly without brute-forcing for every number, which would likely make the code orders of magnitude faster. But I didn't want to also brute force through every combination of divisors, and rather figure out a neat way to get even that on the first go or at least with linearly increasing search time (in other words, I wanted to crack the "balancing act" mentioned in the video)... At that point I left the problem "for later" and never came back.

[@seanm7445]

Poll: What is your favourite band? And why is it Mobius?

[@bsharpmajorscale]

Bands? It's all aböut the LÖÖPS, bröther.

[@thesolarfutureenthusiast1102]

You can't beat a strip. I was always a fan of Placebo myself but, Mobius are the real deal.

[@dootnoot6052]

*slams fist on table* MORE BAND

[@IcyMidnight]

Looking forward to your four dimensional band, Matt!

[@MotoCat91]

I found a few interesting rules for working out the lowest possible number ( i ) depending on the input: First I'd check if the original input ( N ) was odd or even, then how many divisors that number has For example: 13 is odd with 2 divisors (prime) and the rule for all odd primes is: 2^(N) / 2 = 2^13 / 2 = 262,144 For 9, an odd number with 3 divisors (Which ends up being any square of a prime): ( 2^sqrt ( N ) / 2 ) * ( 9^( ( sqrt ( N ) - 1 ) / 2 ) ) = ( 2^3 / 2 ) * 9^( ( 3 - 1 ) / 2 ) = ( 8 / 2 ) * 9^ (1) = 4 * 9 = 36 For 22 (or any even number with 4 divisors): 2 ^(N/2) * 1.5 = 2^11 * 1.5 = 2048 * 1.5 = 3,072 For 12 (and any even number with 6 divisors, where one of those divisors is 4): 2^(N/4) * 7.5 = 2^3 * 7.5 = 8 * 7.5 = 60 I was in the process of writing a program that could figure out these rules on the fly rather than pre-programming each one into a giant switch-case but after 20+ hours of solid work I got distracted by gaming and forgot about it until today. I'm still certain there is a way, but don't have the motivation to continue.

[@kjth2003]

I submitted the correct answer and also emailed in code that would give you the correct answer but on the leaderboard (username kjthoward) I only have 500 participation points..?

[@MarcRidders]

Sorry for nitpicking but at 11:47 in the video the value of 2^63 in the right-most column in the table should be 9,223,372,036,854,775,808

[@mrWade101]

I just searched wiki for "Highly composite number" and took the one at 64.

[@owensilberg2966]

Same

[@thumper8684]

You take the list of primes, you add a list of squares of numbers in the list, and squares of numbers in that list etc. Put them in order. Pick the fist six on the list and multiply them together. For 2 to the power n, you take the first n numbers. For 3^n you need p^2 and cubes of those. For powers any prime P you need p^(P-1) and any previous number to the power P. For compound numbers use the same lists. But be careful. You have to choose which prime to apply to each factor. For example if you want 6 factors, 6 = 2 times 3. This could be 2 times 3^2 = 2 times 9 = 18. It could be 2^2 times 3 = 4 times 3 = 12. It could not be 2 times 2^2 = 2 times 4 = 8. 8 has four factors. I have not explained this well.

[@tana.wattanawaroon]

I did it this way too, and I was surprised nobody this was not in the video so I scrolled down to check the comments. (And, of course, I still wrote code to double check.)

[@elijahbedinger7951]

I wonder if you can make a program that uses the prime factorization method and not the counting up method. I would like to see it.

[@jacobsiemons687]

That's the basis of the program I made, and it ended up being a very efficient method (it solves the problem for arbitrary numbers of factors, not just 64 factors)

[@elijahbedinger7951]

Cool

[@lowercaserho]

I recognise that the band was a joke and a lot of people seem to have had fun with it, so I'm not mad about it. I really hope, though, that it's had it's time and we don't see it making a comeback in the future. It really is an accessibility nightmare. (Autistic person with major audio processing issues here, and I know that on a bad day I simply wouldn't have been able to get through this video.)

[@SoleaGalilei]

Does seem a bit rude to do the music again after he acknowledged he knew it was an accessibility issue. Not really funny.

[@benh8312]

I would bet that quite a few of the 22% who got it wrong put 30,030, which is 2*3*5*7*11*13, the first 6 prime factors multiplied together. 64 is 2^6 and every new prime factor added doubles the number of overall factors, so this would give this number. (That's the way I solved this problem) Edit: I apologise if Matt basically explains this in the video and I missed it while writing this comment

[@thinboxdictator6720]

and now for something completely different

[@martinlamb6122]

When I did this, I thought of binary choices. I immediately discovered 6 distinct primes gave six binary choices, aka 64 options. That gave me a ceiling of 2x3x5x7x11x13. Then it was just a question of creating more binary choices with non-distinct primes to replace the larger primes entirely. As shown in the video, I found a prime w/ exponent n gave n+1 choices. So you have the pattern of exponents 1, 1+2, 1+2+4,... all giving choices that are powers of 2. So the cheapest option was to look at 2 (smallest prime), and as 2^2 is much smaller than 13, you can substitute it. However, adding more 2’s is clearly a bad idea, as the next step would have to be 2^4, which is larger than 11. Moving to 3’s, 3^2 is less than 11, so we can substitute. But now we’ve run out of prime powers less than 7, so that must be optimal: 2x3x5x7x(2x2)x(3x3). My favorite way of thinking of the exponent method is considering how choosing how many primes to use out of n is the same as choosing a log2(n+1) digit binary number, so p^3 gives 2 digits, p^1 gives 1 digit. So the 2’s and 3’s give 4 digits and 5 and 7 give one each for a total of 6 binary digits. 6 digits in binary can represent the numbers 0 to 63.

[@malignusvonbottershnike563]

I was lucky because I already knew that 2,520 was a highly composite number, so I worked out the factors by hand (there were 60), then tried 5040, then 10080, then finally 7560. Was tempted to look up the answer, but I had some time on my hand, and the maths wasn't difficult, so I decided not to waste the opportunity to practice my times tables!

[@1996Pinocchio]

Not gonna lie, the marching band music was funny, and I enjoy that you are experimenting with your videos. It was just really hard to understand the words you were saying (:

[@secondengineer9814]

I demand more band

[@willemkossen]

I looooooove that band music!!!!!

[@tr1x_trl]

I wrote some code for this one and managed to answer pretty quickly

[@TheCrewdy]

I was waiting for the answer to be 7559 - You only require 7559 performers because you yourself are also involved bringing the total to 7560. I thought it was going to be another negative deposit moment!

[@danielyuan9862]

I thought it was 7554 because Matt asks us how many people would be needed to join the band of the original 6.

[@TheCrewdy]

@@danielyuan9862 You should get bonus points for the pragmatic timesaving aspect of recruiting 6 people who already are trained in marching band formations

[@gwenparney4891]

I, the clear master of following directions, read the problem about 6 times - before writing code for and submitting the lowest number with 64 *distinct factor pairs*, not distinct factors, which would've been much easier to code...

[@menachemsalomon]

Curious: For those that wrote (and submitted) a program that finds the solution, are there stats for which languages were used? Personally, I used shell script, ksh flavor with annotations for bash.

[@DaviddeKloet]

I used python but had a stupid bug (I didn't realize I was comparing a number to a function instead of a number to a number) and then switched to C++.

[@Krebzonide]

I solved it by going to the wikipedia page for highly composite numbers.

[@SourceOfBeing]

I figured that the correct answer would have to have 2, 3 and 5 as factors, and then I figured it would likely have 7, 11 and/or 13 as factors as well so I used a website to give me the first 100 multiples of 210, 330 and 390, and then used another website to find out how many factors those numbers had.

[@danielyuan9862]

Did anyone else put int 7554 because they thought Matt was doing some kind of shenanigans and wanted us to answer how many people you want to ADD to the original 6 people in the band?

[@dieb7843]

Have I missed the table of numbers submitted?

[@pm71241]

I like marching band music.

[@jamesthomas8536]

I believe Lizzy Morland's python script has an error resulting in the permutation count for a square number being 2 greater than it should be. Ithink the special case for square numbers should actually reduce the count by 1 rather than increasing it.

[@JoshBlasy]

python one-liner to check all numbers up to 10,000 for exactly 64 factors: [i for i in range(10000) if len([j for j in range(1,i+1) if i%j==0])==64][0] the 10,000 is arbitrary but if you weren't sure you could just put larger and larger numbers in if necessary

[@sergey1519]

Actually you can replace 10000 with 9**9 to save 1 char

[@Parax77]

You can keep your rectangle Numbers.. My band can do rows at 60 degrees.. and is able to march in Triangle numbers (and hexagons too)..

[@bsharpmajorscale]

Matt Barker's Maths Buzzles

[@ShahrukHossain]

Oh crud, I was working on a submission but got distracted by work and missed the deadline :/ I was trying to generalize to higher dimensions AND different orientations of band members but got stuck on deciding on what the orientations (lying down, standing, doing a handstand etc) the band members could be in haha

[@jypsridic]

I'm glad I was wrong because I didn't know how to figure out what the smallest number with 64 divisors is rather than because I didn't know what the target was.

[@niklaskoskinen123]

I'm kinda disappointed that the solution was a highly composite number. Made it way too easy to just Google the solution.

[@feliciabarker9210]

I did it Martina's way, and then managed to miss that 3^3 was smaller than 11, so ended up with 9240 like a twit.

[@labbymousie]

ye same here T_T

[@NetAndyCz]

2:14 I am irritated that the bigger number, or the total is ~78%. It really bugs me that the ~78% part is not attached to the correct answers part.

[@TheSkipinatorVids]

Didn't we see James' logo in a Maths Mistakes video?

[@TheosoMop]

MORE BAND

[@MushookieMan]

I did it by hand.

[@LineRider0]

7:36 there's a similar trick to find the sum of all the factors (of 1944) (2^0 + 2^1 + 2^2 + 2^3) * (3^0 + 3^1 + 3^2 + 3^3 + 3^4 + 3^5) = 15 * 364 = 5460

[@sergey1519]

And i believe product is just N^(number of factors / 2) or something like this? Once you know prime factorization it's much easier. It is much harder to actually factor big number tho.

[@ceilidh169]

I had recognized it would be a highly composite number and so I went to the Wikipedia page for that and saw which one had 64 factors

[@Royvan7]

i programed something out in haskell to list all combos of factors by prime factorizing and recombining. quickly realized that my code must have been missing some combinations when the smallest number with 64 combos was 17,280. thought that was too big to be the intended answer. did get around to debugging my code and figuring out what combos it was missing. Edit: argument my code using martina's method. interestingly the method i was using only messes up 9.46% of the time for numbers 10,000 and under. a bit frustrating. still haven't bothered to figure out what cases i'm missing yet.

[@CravingBeer]

7560? Even Hawkwind haven't gone through that many members.

[@Jack_Cats]

Look mom, I'm on TV

[@SKyrim190]

Sees the James Explains logo All the engineering nerds: Am I a joke to you?

[@stephenhousman6975]

The problem was easy programming a general solution to this type of problem was hard.

[@LunarChimera]

I made a small web app that I tried to send in but it was denied by email as a zip file :/

[@TheSkipinatorVids]

100224 band members? Must be a 70's funk band.

[@kevinmartin7760]

I find it irritating that the top 21 was not presented as three columns of 7 entries...

[@_anastos]

As the person in 22nd place, I take offense to that top 21 list.

[@DaviddeKloet]

If you're Mark Anastos, you're actually in 23rd place at position 22. ;-)

[@_anastos]

David de Kloet Oh you’re right. I take *slightly* less offense now. :)

[@mikelocalypse]

When trying to work out ways to come up with the answer, I realized if you multiply prime numbers in sequence, the number of divisors of the product is equal to 2 raised to the number of primes multiplied (example: 2x3x5 is 30; 3 primes multiplied; 2^3 is 8; 30 had 8 factors). So I made a guess based on this observation, which was 30030. Not even close 😂

[@andrewwebb2141]

Kept waiting for a giant cartoon foot to drop 😀

[@LimeGreenTeknii]

OK, but I want Matt to become part of a marching band

[@b2gills]

My Raku code makes the example Python code look very verbose. say (1..∞).first({ sum( $_ X[%%] 1.. $_.sqrt.​Int ) * 2 - ($_.sqrt.narrow ~~ Int) == 64 }) It is functionally almost exactly the same as the Python code, only mine has -1 instead of +1. (It has to do with the difference with how ranges work in each language.) The cross meta operator ｢X｣ combined with the divisible‑by operator ｢%%｣ really helped to make it tiny. Note that I was not trying to create something small. I was just playing around trying things in the REPL, and I ended up with this.

[@keetrandling4530]

Maty throwing Diana under the bus!

[@galoomba5559]

Could've got into the top 21 if i didn't forget about the puzzle for the first 2 hours or so :/ oh well

[@theunknown4834]

spreadsheet is too easy A1-SUM(ARRAYFORMULA(CEILING(MOD($A1/SEQUENCE(1,$A1),1)))) put A1 as 1, A2 as 2 and so on. Auto fill until 64 is found (I did from 1-10000) basically, it divides by all number from 1 to the number and check if it is an integer.

[@worstwordmonger]

I had found the correct answer, but then for some reason convinced myself it was wrong and I was actually looking for a number with 32 factors. Not one of my best moments lol

[@PronteCo]

Wait so was this the last one?

[@DaviddeKloet]

For the last few weeks the website has been saying there won't be a puzzle this week but there will be one soon. I'm confused as well.

[@alwinpriven2400]

sad, my shakespeare code didn't get in

[@Electronieks]

Top that the band is gone

[@fdagpigj]

I feel like the point decay is a bit too powerful at 20% per week. The first seven puzzles are worth less than the latest two.

[@pdpgrgn]

I like the current system of points. For people who are competing for the top spots since the beginning, the points from the ancient puzzles still matter. For people who sumbit one off solutions to see if they can get it right or not, they are likely to be indifferent to how the scoring works. And for people who discovered the series midway, the handicap isn't too big over long term

[@Adderkleet]

I realised it was about factors/divisors. I knew there would be a list of "numbers of divisors for each number". And I still managed to be in the ~20% of incorrect answers. Drat.

[@murphygreen8484]

Hmmm, somehow I got 83,160? Obviously something went wrong with my code

[@jacobsiemons687]

That's the smallest number with 128 factors, so I suspect your code is very nearly correct

[@murphygreen8484]

@@jacobsiemons687 huh, if I change my code to look for 32 unique configurations instead of 64 I get the correct answer

[@stevemarethyu3003]

@@murphygreen8484 I think that's because you don't want unique combinations since the direction matters.

[@carlsb3rg]

The Parker Guarantee :)

[@Fabelaz]

Yup, looks like a lot of people just knew the solution already so didn't need to figure it out. Meanwhile I was one of the wrong ones. Hey my number is completely wrong.

[@mrmonster3434]

If you acknowledge that the too-loud band music causes genuine problems for some of your viewers, why deliberately include it multiple times in this video? Take some damn responsibility for what goes up on YOUR channel.

[@bufar]

The only thing he said while the music was playing was an apology for the music playing. It doesn't obfuscate any of the solutions or explanations.

[@Mical2001]

I made a webcrawler that went through numberempire.com and scanned every integer page that existed until it found one whose Count Of Divisors was 64

[@Mical2001]

This comment is just to ruin the joke for the sake of honesty. I didn't actually do this, but it's funnier to say that I did.

[@kevinkor2009]

If you keep using that music, you'll be band.

[@Reubs1]

Numberphile has a video covering the stuff about the combinations of exponents: kzbin.info/www/bejne/aHuwY6J_osdsh8k

[@SpreadFriendliness]

ah crap i was so confident i had the correct answer! my answer wasnt wrong, but it wasnt the smallest!

[@FX9426]

I hate myself when I try to get the speed bonus, and then got the wrong answer. Me is so stupid

[@FelixJuggler]

Today I learnt that: '4 is 1 more than 3' 😎

[@alexpotts6520]

Corollary: 3 is one less than 4.

[@FelixJuggler]

@@alexpotts6520 Genuinely blown my mind

[@amarpersaud2950]

I knew of the prime factor exponents but got lost after 2^63 and went :•| just wrote some code

[@brenthooton3412]

The band music has been banned.

[@ProzDemon]

That visual explanation didn't really work for me. Colourblindness is a curse...

[@tzisorey]

Needs more cowbell.

[@DukeBG]

i solved this puzzle on my phone in bed and it seems the result was correct. yay. easy.