Multiplicative Persistence (extra footage) - Numberphile
HTML-код
- Опубликовано: 21 окт 2024
- Main video: • What's special about 2...
Matt's book: bit.ly/Humble_Pi
This video follows our main Numberphile video with Matt Parker.
Parker Square video: • The Parker Square - Nu...
Parker Square T-Shirts are at: teespring.com/...
Hear Matt on the Numberphile podcast... bit.ly/Numberph...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Support us on Patreon: / numberphile
Brady's videos subreddit: / bradyharan
A run-down of Brady's channels: www.bradyharan.com
Sign up for (occasional) emails: eepurl.com/YdjL9
9999 has a Parker Persistence of 3?
A parkersistence, perhaps?
OrangeC7 parkerhaps
@@DavidSavinainen:
"Is three the correct answer?"
"Parkerhaps..."
Parker persistence of 4 :p
It's even alliterative! This is fantastic!
I love how every time he makes a mistake he puts the suggested link to the Parker Square.
I will never get tired of hearing Matt Parker talk about maths.
Suggested video: the Parker square
That *_was_* the mascot
It just rolls off the tongue so well.
Every video is about a number tho
So a Parker multiplication???
Parkerplication.
Parkerplication, a subset of Mattematics.
More like Parker's persistence
How about a Parker Product?
The career change to comedy / outreach seems pretty committed, that's for sure.
1:15 Matt wanted to say 'its all about the base'
Don't think so man.
No treble...
All your base are belong to Matt?
lol
When I watched the first video I thought about starting from down up, and then I got to the realization that you need to stop whenever you encounter a prime bigger than 10 (or, of course, bigger than 7). And then I saw this video where Matt told me exactly that, and it made me happy because I'm awful at math but I have it a go anyway, and I think he would be proud!
Well I'm proud of you, I mean I'm nobody of relevance in maths, but still. Proud of you Penguin.
It's so comforting to me when "Suggested: The Parker Square" shows up in the top-right.
I wrote up my code before watching this extra footage. Everything I thought I was clever for doing was mentioned in this video.
Theres a general rule in the realm of making things: if you could figure it out quickly, it wasnt clever. Have found this out many times!
@@mitchellsteindler A-yup. Me too. When I was 10 or 11 I was looking to generate the primes in order. So I just did a while loop and increased the number by 1 every iteration. Well! Being the smart kid I was I realized I didn't have to test any of the even numbers because none of them were prime (except of course). So I started incrementing by 2 instead! Oh and I only have to look for factors up to the square root of the number I'm looking I'm looking for! Ho, ho, ho! I'm so smart!
Except, yeah, everyone already knew this.
@@mitchellsteindler had never thought of it like that
Mitchell Steindler Unless you are a genius, then the rule does not apply, I guess.
Wait. So things aren't clever if you figure them out quickly?
Just because other people have already figured something out, doesn't mean you're not clever when you figure it out for yourself.
We need a programmingphile channel Brady! I loved this video for the coding!
Fixed the recursion and put it in python 3.x if anybody is interested:
def persistance(num, steps=0):
if len(str(num)) == 1:
return steps
else:
steps += 1
digits = [int(i) for i in str(num)]
result = 1
for j in digits:
result *= j
return persistance(result, steps)
I have made a program to search for some numbers, and I am now almost certain that the conjecture is true.
First observation was also made in the video. All prime factors of the digital root of any number are less than 10. So the only possible prime factors of a digital root are 2, 3, 5, and 7. Now comes the important corollary.
If we have a number of multiplicative persistence n, then its digital root must have the following properties.
1. It has multiplicative persistence n-1.
2. The only prime divisors are 2, 3, 5, and 7.
So the question becomes whether there exists a number of multiplicative persistence 11, for which the only prime divisors are 2, 3, 5, and 7. Since we require the multiplicative persistence to be greater than 1, in particular none of the digits of the number can be zero. So we can limit our search to numbers with the following properties.
1. None of the digits are zero.
2. The only prime divisors are 2, 3, 5, and 7.
Let us call such numbers candidates.
Here comes the punch line. The set of all candidates appears to be finite. I conjecture that 31262221321885653647626425815737111943458241183262682285162767533715254994149452428386848427865279586287233185834769954797571297422117699584, which factors into 2^25*3^227*7^28, is the largest candidate, which would mean there are 12614 candidates in total. The reason I so strongly believe this is that this number has 140 digits, and by exhaustive search I can conclude with certainty that there exist no larger candidates with at most 300 digits.
Assuming my conjecture holds, the function f such that f(n) is the amount of numbers of multiplicative persistence n for which none of the digits are zero and the only prime divisors are 2, 3, 5, and 7 is well-defined. We can also calculate all of its non-zero values.
f(0)=9
f(1)=
17
f(2)=
11997
f(3)=
388
f(4)=
134
f(5)=
40
f(6)=
12
f(7)=
8
f(8)=
5
f(9)=
2
f(10)=2
Here f(10) corresponds to the numbers 4996238671872 and 937638166841712. Note that the first of the two also appears in the video. Also, f(9) corresponds to the numbers 438939648 and 231928233984 and f(8) corresponds to the numbers 4478976, 784147392, 19421724672, 249143169618, and 717233481216.
I want to finish off with a heuristic argument why, in every base, the set of candidates is probably finite. I start with the following observations.
Let n and N be natural numbers. Then there are O(log_n(N)) numbers of the form n^k
I have now optimized the search algorithm to find all candidates of at most d digits. It now requires O(d^4) time and O(d) space. It finds all candidates of at most 250 digits in 3 minutes on my laptop. I will leave it running over night to see what it can find.
Do note that, if there are no new candidates of at most d digits, then there are no numbers of multiplicative persistence 12 of at most d*log(9)/log(10) digits. For example, since I already checked there are no new candidates of at most 300 digits, I know there are no numbers of multiplicative persistence 12 of at most 314 digits.
I was fascinated by your work here so far. I found this on the OEIS and thought it might help you strengthen your conjecture:
From David A. Corneth, Sep 23 2016: (Start)
For n > 1, the digit 0 doesn't occur. Therefore the digit 1 doesn't occur and all terms have digits in nondecreasing order.
a(n) consists of at most one three and at most one two but not both. If they contain both, they could be replaced with a single digit 6 giving a lesser number. Two threes can be replaced with a 9. Similarily, there's at most one four and one six but not both. Two sixes can be replaced with 49. A four and a six can be replaced with a three and an eight. For n > 2, an even number and a five don't occur together.
Summarizing, a term a(n) for n > 2 consists of 7's, 8's and 9's with a prefix of one of the following sets of digits: {{}, {2}, {3}, {4}, {6}, {2,6}, {3,5}, {5, 5,...}} [Amended by Kohei Sakai, May 27 2017]
No more up to 10^200. (End)
From Benjamin Chaffin, Sep 29 2016: (Start)
Let p(n) be the product of the digits of n, and P(n) be the multiplicative persistence of n. Any p(n) > 1 must have only prime factors from one of the two sets {2,3,7} or {3,5,7}.
Can you send me the program?
You should write a paper.
When you limit the size of the number, of course the candidates are going to be finite. What does not follow is, their will be no numbers of the form 2^a*3^b*5^c*7^d over 300 digits that do not include a zero. Their are clearly an infinite number of numbers without 0 in them, their are also clearly an infinite number of numbers with the factors 2, 3, 5, and 7. What has not been demonstrated is that these are distinct sets that have practically zero overlap.
277777788888899 has a prime factorization of 13*59*1699*213161503, which isn't ideal. It also doesn't matter where you put the 2 (so long as you keep the order of 7s, 8s, and 9s fixed), as all of them have at least one prime factor greater than 7. I had hope for 777777888888992 since it was divisible by 2^5, but the next smallest prime factor after 2 was 3457. (It's full prime factorization is 2^5*3457*23689*296797 which, again, is not ideal.)
Nice
Technicaly, for this purpose 2*7*7*7*7*7*7*8*8*8*8*8*8*9*9 is 2*7*7*7*7*7*7*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*3*3*3*3, soo... maybe this :27777772222222222222222223333 will be better.
That will be exactly the same We need something which survives 12 steps and, because it's exactly the same, it will only last 11 steps. Factoring is important because, if you can find an 11 step number with only single digit prime factors, you'd be able to construct a 12 step number. @@eryksoowiej4427
@@deathpigeon2 It's prime factors won't be exactly the same though.
Xeridanus exactly what I ment.
I did a bit of code for myself. First, the semi-naive approach you suggested. There are two kinds of numbers with a persistence of 11: those which have a digit product of 937638166841712 and those which have a digit product of your 4996238671872. I tried all possible numbers with between 0 and 250 copies of the digits 2, 3, 7 in ascending order, and there are only two such outcomes. Out of curiosity, I found that there are only nine different powers of 7 (tried everything up to 7^30000) which do NOT produce a zero in the product: 7^1, 7^2, 7^3, 7^6, 7^7, 7^11, 7^19, 7^35. Out of those, 7^35 and 7^19 have 5s and 8s/2s which will produce zeros on the next iteration. Similar patterns appear slower for 2^n and 3^n but they deplete very quickly.
Yep, I had the same idea. This is what I found:
Persistence of 6: 27648 = 2^10 * 3^3 * 7^0 (5 digits)
Persistence of 6: 47628 = 2^2 * 3^5 * 7^2 (5 digits)
Persistence of 6: 64827 = 2^0 * 3^3 * 7^4 (5 digits)
Persistence of 6: 84672 = 2^6 * 3^3 * 7^2 (5 digits)
Persistence of 6: 134217728 = 2^27 * 3^0 * 7^0 (9 digits)
Persistence of 6: 914838624 = 2^5 * 3^5 * 7^6 (9 digits)
Persistence of 6: 1792336896 = 2^10 * 3^6 * 7^4 (10 digits)
Persistence of 6: 3699376128 = 2^23 * 3^2 * 7^2 (10 digits)
Persistence of 6: 48814981614 = 2^1 * 3^20 * 7^1 (11 digits)
Persistence of 6: 134481277728 = 2^5 * 3^6 * 7^8 (12 digits)
Persistence of 6: 147483721728 = 2^16 * 3^8 * 7^3 (12 digits)
Persistence of 6: 1438916737499136 = 2^24 * 3^6 * 7^6 (16 digits)
Persistence of 7: 338688 = 2^8 * 3^3 * 7^2 (6 digits)
Persistence of 7: 826686 = 2^1 * 3^10 * 7^1 (6 digits)
Persistence of 7: 2239488 = 2^10 * 3^7 * 7^0 (7 digits)
Persistence of 7: 3188646 = 2^1 * 3^13 * 7^0 (7 digits)
Persistence of 7: 6613488 = 2^4 * 3^10 * 7^1 (7 digits)
Persistence of 7: 14224896 = 2^9 * 3^4 * 7^3 (8 digits)
Persistence of 7: 3416267673274176 = 2^6 * 3^27 * 7^1 (16 digits)
Persistence of 7: 6499837226778624 = 2^24 * 3^18 * 7^0 (16 digits)
Persistence of 8: 4478976 = 2^11 * 3^7 * 7^0 (7 digits)
Persistence of 8: 784147392 = 2^6 * 3^6 * 7^5 (9 digits)
Persistence of 8: 19421724672 = 2^21 * 3^3 * 7^3 (11 digits)
Persistence of 8: 249143169618 = 2^1 * 3^2 * 7^12 (12 digits)
Persistence of 8: 717233481216 = 2^9 * 3^5 * 7^8 (12 digits)
Persistence of 9: 438939648 = 2^12 * 3^7 * 7^2 (9 digits)
Persistence of 9: 231928233984 = 2^33 * 3^3 * 7^0 (12 digits)
Persistence of 10: 4996238671872 = 2^19 * 3^4 * 7^6 (13 digits)
Persistence of 10: 937638166841712 = 2^4 * 3^20 * 7^5 (15 digits)
There are:
139 numbers with persistence 4
41 numbers with persistence 5
12 numbers with persistence 6
8 numbers with persistence 7
5 numbers with persistence 8
2 numbers with persistence 9
2 numbers with persistence 10
Given how low most exponents are, it's very likely that there aren't any more numbers than these.
"i Suggestion: The Parker Square - Numberphile"... hahahahahaha
Brilliant book plug, honestly 😂
Numbers with a 5 in them don't have to generate numbers with a 0 in them, there must be an even digit as well. For instance, this chain has odd digits only: 3335 -> 135 -> 15 -> 5. I haven't found an example with a longer chain though.
You can't have 5 and an even digit. It's easier to ignore 5.
it's not only "5 and an even digit", you also have to make sure that all the other numbers you have don't give you an even number when you multiply them: 599 wouldn't work cause 9*9 =81 and 81*5=405
so yes, i too think that not having a 5 makes it easier
@@Morbacounet Can you if you want to prove their cannot be long chains starting off with a number containing a 5? It's clear it's very hard to find chains longer than 2 steps, but does that mean there aren't any?
@@Morbacounet But might you be ignoring a rare set of numbers with one or more 5's, and no even digits, that actually turn out to have large number of steps?
I can clearly see that ignoring any number that has a 5 and any even digit in it does make sense, but surely if there is no even digit in it then the presence of one or more 5's might not be a problem.
355
6:11 and the Parker Square suggestion :p
classical trolling!
I think you already have the mascot for a 'Parker Square' moment: that plane on the front of his book. I can't think of a better one, as not only is it quite fitting, it'll also make sense to people who don't know what -- or have never heard of -- the 'Parker Square'. And I think Matt will approve of the use of the 'airplane' over the 'Parker Square'.
Shouldn't have used the Gaxio, Matt...
The "Parkersistence sequence": Take some number n, add up all the digits, and then follow the persistence pattern from before.
In that respect I have found a number with parkersistence 12: (10^30864198765433 -1) * 10 + 2 (just 30864198765433 nines and then a two)
Matt and James Grime need to do some kind of collaboration vid if their schedules ever allowed it. It would be so cool to have my two favorite Numberphile guests in the same vid.
Loved how it was still three steps!
This will be the first challenge of my mathematical career!
"One day, we will have a mascot for such moments!"
More from Numberphile: The Parker Square
0:23 “You know that could be a fun project, who knows maybe I’ll find it. 233 digits is huge but not impossible to work with”… sees the video is 4 years old… looks it up sees they’ve now checked to 20,000 digits… “yeah maybe I’ll let the people with more computing power than my laptop keep looking”
Thing about prime factors of the number is you can always stick a bunch of ones in it until you find one that does have only 2s 3s and 7s as prime factors. It probably makes more sense to do it the other way around when coding it I.e. generate numbers by multiplying 2s 3s and 7s.
that’s actually pretty smart
Next I think Matt should cover the Parker factorials. 1, 3, 6, 10, 15, 21...
The triangle numbers!
Well plugged book spot
It might be a Parker multiplication, but that was no Parker segue. Because that way the perfect transition into the book ad.
I had a feeling its base. So I made this in python with base8 (oct) and base16(hex) and base 8 seems to have maxed at 6 steps. but oddly, unexpectedly, base16 (hex) has seemed to have capped at 8. why 8?
A classic Parker Square!
There are probably indeed numbers with properties in every number system that can be converted to single digits in maximum steps. In the triple number system, for example, 222, in the quadruple number system, 333. These are usually easier to explain heuristically.
Instead of adding line 7 (steps += 1) I would suggest to change the recursive call to per(result, steps + 1). Same result, but somewhat cleaner.
wrote a little python which does the naive brute force search of the other bases. checked numbers 1 to 100 million:
Base - Persistence - Number
2, 1, 10
3, 3 , 222
4, 3, 333
5, 4, 33334
6, 5 , 24445
7, 7 , 5555555
8, 6, 333555577
9, 7, 2577777
almost linear, but a small sample size
def dig_prod(num, base=3):
"""Accepts and returns base 10 number, converts number into target base
and multiplies all digits together."""
import numpy as np
return np.product([int(x) for x in np.base_repr(num, base)])
1:28 "there's a conjecture that all base 3 numbers above a certain size have a 0 in them."
Is this what he meant to say? That can't possibly be true
111111111111... is infinitely big and has no 0 in it. You are right. However, I have no idea what he meant to say.
Not sure, but it might be hinting at this April Fool's vid they did 7 years ago.
ruclips.net/video/UfEiJJGv4CE/видео.html
He meant to say that all powers of two above a certain size (2^15) are conjectured to have a zero in their ternary representation.
the smallest base 3 number of a given persistence would have to be made entirely of 2s. This makes sense: we only have 0,1,2 to work with in base 3, and any digit being 0 would make the persistence 1, and any digit being 1 wouldn’t change the persistence.
So in base 3, all numbers that we need to check would contain only 2s. That means the resulting number would be a power of 2, represented in trinary. The conjecture is that all powers of two above a certain size contain a 0, so that wipes it out. So he’s saying in shorthand that all trinary numbers worth checking above a certain size have a zero in their first step, which makes them all have persistence of 2.
When you watch such video throwing a challenge at you but it's 2 am
Welp, I guess sleep will wait
How do you leave a comment 2 days ago if video was upload few minutes ago?
These videos are glorious.
Growing them up sounds like a great idea!
*Classiiiiiic* Parker square!
This is the 5000th vid I've Liked!
I bought the book in Budapest!
Despite being a recreational problem, there is some interesting math behind the multiplicative persistence problem, including connections with objects akin to cellular automata. For those interested in the problem, I suggest reading the paper "On Sloane's persistence problem", Experimental Math vol 23 (2014), 363--382.
There one will find more computational evidence, and results for arbitrary bases.
Im going to overgeneralize an overgeneralized generalization:
In the iterative multiplication of the digits of any whole positive integer N, the limit of the persistence of that number N will equal the base (B+1)
As long as that base is equal to or greater than 10.
So P(N)=(B>=10)+1
But since I havent checked above 10 either, so P(N)=(B=10)+1
Thanks for coming to my retarTED talk.
Beautiful thumbnail.
There seem to be 2 different versions of this program, one which prints the number of passes and one that does not. The call to the first one is per(nnn) where nnn is the number to be tested.. This version does not compute and/or print the number of passes. Please tell me the call to version that computes and prints the number of passes. The Def statement shows 2 parameters. What are the corresponding parameters in the version that computed the number of passes.
0:47 That's because any programming language compiler is defined in a way that the type Number has a specific range.
I'm not a Python programmer, but I know that in JavaScript, Java, and C# it's like that.
In JavaScript, you simply have a type "number", which has a fixed range.
In Java, there are some types of numbers, including byte, int and long.
In C#, there are tons and tons of types of numbers.
However, in Java and C#, you can use a library, BigInteger or BigDecimal, which basically tell the compiler to remove the regular range, and instead hand it over directly to the RAM, so the more RAM you have - the bigger numbers you can use while maintaining is the accuracy.
I imagine it's the same with Python's "numpy".
In JavaScript, there are plenty of big number libraries you can use.
However, in V8 engine (Node.js, Chromium, Chrome), a new type of number has been added - BigInt. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt
This means that you don't even need a special library when dealing with numbers, as you can directly do it in the browser, as long as you have enough RAM.
Python uses big integers by default
As far as trying to work backward from N = 277777788888899, remember that in trying to find a number that will produce N on its first step, any permutation of its digits will do just as well as N itself, because after N, the sequence will carry on exactly as with N in that place.
So you have to factor all those (digit-permuted) possibilities, to find one or more that factor completely in single-digit factors.
There are 15!/(2!·6!²) = 1,261,260 such permutations.
Incidentally, the prime factors of N are:
277777788888899 = 13·59·1699·213161503
Fred
There are more possible permutations, because you can break up the 8's and 9's into combinations of 2's, 3's, 4's and 6's. On top of that, you can insert an arbitrary number of 1's at any position.
to remove the seccond print of the last number, just replace it with printing the steps instad of adding another print line.
I saved me the code as a textfile, so i always can play around with it, using my python software.
I think I know of a shortcut. Basically take any of the 11-step numbers, and take all the prime factors. If any of the prime factors are double-digit, move on. Because any 12-step number, well after the first step, you'd get an 11-step number. So any 12-step numbers could be found from the 11-step numbers. Seems more efficient to take a bottom-up instead of top-down approach.
Edit: Just noticed, he mentioned this in the video.
5:38 The Parker Silence...
I love the room you guys are in. Is that an apartment or a college maths closet? Love the aesthetic.
f we cross out from set of positive integers all numbers divisible by 2 and all numbers divisible by 3 then
all remaining numbers (including remaining composite numbers and ALL prime numbers) will be in one of two forms 6k-1 or 6k+1, so it's not suprising that every prime plus or minus 1 is divisible by 6
Was the book supposed to flicker or was that intentional?
Aren't both of those options the same?
@@MrDannyDetail Yes, I was half asleep when I typed that.
@@raydarable it was a real Parker Comment.
I picked 3339933399, I think it was 4 steps. I was disappointed until I saw just how hard it is to get over 2.
My version shows that has 5 steps:
per(3339933399,0)
4782969
217728
1568
240
0
0
Total Steps: 5
Additionally, 9,999,999 gives an identical result at 7 digits instead of 10.
@@rogerdotlee I think you mean 999,999 (six digits). 9,999,999 is only three steps.
@@rogerdotlee remove the "print n" under the if lol
Is there a math theorem about prime factorizing numbers after adding certain digits to them? For example, if we add a a couple of 1's to 277777788888899, could it eventually become a number that can be prime factorized by 2's, 3's, 5's, and 7's?
Okay, just as I posted it, I realized that 2 and 5 are impossible, since we can check the last digit. To become divisible by at least one 3 you'd have to add 1+3x ones. That means that for all other cases, you need to get a number that is equal to 7^n. My suspicion is that this trick won't work, but other modifications might still work. If I move the 2 to the back I at least get a number that is divisible by 2.
I'm still game to find the biggest number.
You only have to check numbers of the primes 2,3, and 7.
So 2^x * 3 ^ y * 7 * z with x, y, and z in a sufficiently small range like 0 to 54 will produce all possible results.
The only two largest numbers I could find this way were:
937638166841712 and 4996238671872. Both take 10 iterations to complete.
937638166841712 is the largest of those two. 2^54 is larger than this. Therefore if there would be any number whose digits multiply to that number it should be smaller than 2^54.
Unfortunately, there are none that do.
I bought the Audible version of the book!
Looking at base 3 it's obvious the only numbers we care about are ones where all digits are 2 because 0 results in failure and 1 does nothing. This means we only need to find the numbers which are powers of 2 that have no 0's written in base 3. The numbers I found currently are
2 (2), 4 (11), 8 (22), 16 (121), and 32,768 (1,122,221,122)
I have not coded this, I checked every number up to 2^30 by calculator. 8 (22) is particularly interesting as it is the only time (to my knowledge) where a number containing only 2's will itself be a power of 2. This is because number containing only 2's can be written as (3^x)-1 where x is the number of 2's. Every number containing all 2's will immediately be followed by the introduction of a new place value which in base 3 is a power of 3. This also gives 222 the largest multiplicative persistence I could find.
26 (222) -> 8 (22) -> 4 (11) -> 1 (1).
Base 4 is a really similar problem, the only numbers we care about are ones that only contain 3's or contain 3's and exactly one 2. Any number with more than one 2 becomes a factor of 4 when multiplied and every factor of 4 in base 4 ends in a 0. Thus we only care about numbers which are powers of 3 and powers of 3 doubled that also have no 0's. I found [by hand]
6 (12), 9 (21), and 27 (123)
With 63 (333) having the largest persistence I could find
63 (333) -> 27 (123) -> 6 (12) -> 2 (2)
"Let's just spontaneously fix that in the edit" lol
If you ever want to search for longest result, write the code in C or even assembly, the code won't be too long and it will run orders of magnitude faster than python
It's takes more time to learn C first 😂
Python has big integers, and Pypy can compile it. C or assembler don't, so you'll be calling an arbitrary precision library like gmp, and the difference becomes insignificant after you hit big numbers. Close to metal isn't magic.
That said, try Julia or Haskell. And for a task like this, maybe Decimal instead of Integer.
@@00O3O1B If you're doing that level of assembly work (I have), the answer is typically get a bigger microcontroller or stop toying with the CPU and use the GPU already. Which can be eased greatly with e.g. Clyther or OpenAcc.
Searches like these are embarassingly parallel so distributing it easy, and offers gains in thousands compared to cpu fiddling often 2-5x. Algorithmic work is often more significant still.
Yes. I wrote my code for this in C, but I had to operate on arrays of integers that represented base-million digits (like digit[2] = 277; digit[1] = 777788; digit[0] = 888899;)
I also reduced search space as Matt described in main video, and with other optimizations it allowed me to search all numbers up to 300 decimal digits within about 15 minutes.
Spoiler: my conclusion was that searching further is a waste of time.
Instead of adding a new parameter you could have just always returned one more. So:
return per(result) + 1
And in the beginning instead of returning done, which is pretty much useless instead return 1 (or 0 whichever is the correct one)
Or do per(n,steps+1)
@@killereks The recursion is already "counting" how many times the persistence happens, @Sinom is just suggesting getting the function to accumulate and report that count when it returns back up the chain.
What you're suggesting is just another form of what Matt already did, which is getting each recurrence of the function to calculate an extra step, and then printing it out at the base case before the returns happen. And again, they'll happen regardless; passing that parameter is missing an opportunity to make the code more efficient.
This sort of thing can actually matter in larger programs, so programmers often try to think about things this way.
@@KyleJMitchell i know what sinom suggested but i think Matt's way is more readable
@@killereks if you program using functional paradigm, sure
otherwise, it is just a way of showing you would rather write a loop than a recursion
no problem doing that either, but the recursive way is as sinom suggested for its mathematical iterative numerical method's resemblance
@@RadeticDaniel using recursion you might run into an overflow which is annoying
Did some research myself. generating numbers starting with 1 and then multiplying by digits 2..9 until a 0 appears in the number. This stops quite fast. 4996238671872 (first multiplication of the digits of 277777788888899) being part of this set. Total set size is just 2584 items. If I did things right the only possible way to find a number with more than 11 steps is one that is huge does 12 or more steps and then drops down to 0.
Was this video reuploaded 3 days after it was originally uploaded?
Maybe patreon something something? Often I notice videos in this channel are unlisted
@@alicewyan It can't be that. This video was uploaded to youtube 3 days ago. I saw it myself.
Classic Parker Square
9999 > 36 > 18 > 0
9999 > 6561> 180 > 0
Miraculously though, it's still the same number of steps, and the second step is only off by a factor of 10. That's kind of neat.
1*8=8 though, not 0
@@supermarc Uuuuuh
ruclips.net/video/PTAXUYLbFYk/видео.html
@1m35s: "...all base 3 numbers above a certain size have a zero in them..."
Counter example: 222......222(base 3) where the length is just above "a certain size". I have other counter examples if required.
I thought that at first, since he didn't really explain that, but I think what he meant was that once the length is 'above a certain size' then all base 3 numbers will, when their digit are multiplied together, create a second number with at least one zero it in, which dooms them to be a 2 step number, since they go to 0 in the second step.
I love Matt
I always pronounced numpy as "num-pee" because it sounds funny, like lumpy
You like pee? I like pie
@@00O3O1B I'm aware what it's SUPPOSED to be and why, I just like mine better
I see Matt is already working on his 2nd book in the Humble Pi series of math bloopers.
Is there a record for additive persistence? You know, like Multiplicative persistence but adding all the digits instead of multiplying them? Or is it too easy to increase the additive persistence by adding a digit?
277777788888899 doesn't have any single digit prime factors, so it can't be part of any chain of length 12 or more. Only numbers of the form 2^n * 3^m * 7^p can be the second number of any chain of length > 3.
You can also have 3^m * 5^q * 7^p, just never 2's and 5's together (though these numbers are unlikely to be the smallest since they don't lead with a 2)
Eg:
355
75
35
15
5
We need to remember though that it isn't that number... It's those digits. The only reason is arranged that order is because they're looking for the smallest one. 998888887777772 is just as valid as a choice of a number with a persistence of 11 but it's much bigger. Is there a way of rearranging 277777788888899 to give us a number of the form you mentioned? I suspect not but it's worth investigating...
@@MEver316 It's not, but I wasn't claiming that. However, if you multiply the digits of 277777788888899 together, you get 2^19 * 3^4 * 7^6, which is the second number of a chain. Given a number of the form 2^n * 3^m * 7^p which forms a long chain, it's easy to find the smallest number which reduces to that. Every number in a chain which *did not start the chain* will be the product of only single digit primes.
@@MEver316
You can not only rearrange the digits but also replace any 8 with 222 or 24, any 9 with 33, any 23 with 6 etc. and you can inject any number of 1s.
So, to have a p12 (number with persistence 12)
you need a p11 (number with persistence 11)
that is the product of powers of 2, 3 and 7 (or 3, 5 and 7).
Those can be easily tested with 3 nested "for" loops, using n*m*p steps.
For n, m and p up to 300 only the following 2 numbers have persistence 10:
4996238671872 = 2^19 * 3^4 * 7^6
937638166841712 = 2^4 * 3^20 * 7^5
2^19 * 3^4 * 7^6 can be changed to 2^1 * 8^6 * 9^2 * 7^6
and those numbers are used in 277,777,788,888,899
The growing up works, but you need to consider every permutation of the numbers along the way
I have checked multiplicative consistency for various bases and found following results (consistency may be more):
Base Consistency
2 1
3 3
4 3
5 6
6 5
7 8
8 6
9 7
10 11
11 13
12 7
13 15
14 13
15 11
16 8
17 17
18 10
19 19
20 14
21 16
22 15
23 18
It is clear that if a prime number is taken as base, it has more iterations till it reaches single digit.
As expected, base having more number of prime factors will increase the chances of multiplication to be zero and break the chain there itself.
e.g. for a base 10 number, if 5 occurs with any even number, multiplication will have zero in units place and will end the chain.
similarly for a base 12 number, having 3 with 4 or 8 OR 6 with 2 or 4 or 8 will cause similar effect.
What program did he use to type the code on?
I hate when vid makers take out the math, or the science, or the supposedly tough brain work. Thank you for making a workaround for keeping the original vid watchable by the plebs, while letting the nerds nerd on.
I picked 47, it had three steps
Not bad! According to the other video, 39 is the smallest. (I had to go back and check)
whats the smallest number with the most multiplications before you reach 0-9?
I tied the number on the fronts of digits and persistence with 466,777,777,888,889.
Surely, there will be a massive number where the digits multiplied together will give 277777788888899? Could you not repeatedly divide it by 1-digit numbers and then concatenate those 1-digit numbers, then put the result from the final division on the end, and that is your new number?
For instance, take the number 10. 10÷5=2, so 52 has a persistence of 3 (5×2=10 and 1×0=0). Is it not possible to do the same thing with 277777788888899?
I thought the same thing, but I also realized that you aren't constrained by the order of the digits of this number. Matt did mention to look for the prime factors, so if we could find a number in any combination of these digits that had all prime factors of 2, 3 or 7, (we know we won't find 5) then we could just concatenate the digits. That wouldn't guarantee that it would be the smallest number, but it would prove that you could get to a 12th step. If the prime factors are small enough (like 3 and 2) we could multiply those to get one less digit.
He's gone and Parkered it!
Could you not take this maximum number (2777....) and try carefully adding single digits to see if you can get away with more than 11 steps? Obviously whatever number with 12 more steps would be larger than the current record holder?
1:30 "There's a conjecture that all base three numbers above a certain size have a zero in them." - umm, what?? What about a string of twos? Or am I misunderstanding this.
How could you work backwards from 8 to that larger number?
Its not that there is no number, the conjecture is that is smaller than 10^233 that has a persistence of 12.
To find a number with 12 steps why notfind a number where the product of the digits equals 22777788899?
As others have pointed out, 277777788888899 has a prime factorization which includes primes bigger than 7 and thus cant be the result of multiplying any digits together
I wonder, however: since it is base-dependant, what is the point of it all? I mean, is looking into base-dependant stuff a legitimate research field? It's an honest question, I wouldn't be that surprised if there were extremely useful insights to be gained by doing it. Any applications I should know about?
It's not always about the result, but about the methods used to reach the answer.
Despite being a recreational problem, there is some interesting math behind it, including connections with objects akin to cellular automata. I suggest you look at the paper "On Sloane's persistence problem", Experimental Math vol 23 (2014), 363--382.
What coding program is that
He's using Python.
Python 3.7.2
@@Rohit-ty6hn Nah it's 2.7 since the print function requires you to wrap your print statement in parentheses in python 3 (e.g. _print "Hello World!"_ instead of _print("Hello World!")_ )
For anyone doing upward propagation, there are 1261260 numbers to check
here i go
Haven't read the book yet. Was there actually an incident where wings were put on an airplane backwards?
OMG I've seen the cover of that book loads of times on his videos etc, and never twigged that there was anything out of the ordinary about that plane!
I guess if we're all at an airport, and for some reason they let a volunteer chose which plane we all fly on, then make sure I don't volunteer lol. I'd have us arriving at our destination by the little tried method of flying backwards away from it until we had gone so far around the world that we would arrive at it from the opposite direction to expected!(Or I guess we could face away from it and reverse towards it, but still.....).
I think we will find numbers with multiplicative persistance of 12,13, even a million, billion, googol, etc but we will end up getting in the zone of unimaginably large numbers like Graham's number, TREE(3), etc
Wikipedia says we have searched till 10^20000, but 10^20000 is nothing compared to infinity so those numbers with multiplicative persistances of 12,13,1000000,1000000000,10^100, etc will be unimaginably large but still finite
Unfortunately, the number 277777788888899 has prime factors 13, 59, 1699, and 213161503. I guess this means, that one can never express that number as a multiplication of digits because of the massive prime factor? For instance, 4996238671872 (the next number), has multiple single-digit prime factors 2^19, 3^4, 7^6.
This would not be such a problem - 277777788888899 having big prime factors - because this is not the only one number, holding a record now, it is the smallest one. What about 271111774928738118871178132? It is practically the same as 277777788888899, it only has a bunch of 1's, placed anywhere, and some of other digits are presented in their factored form - for example, here one of two 9's appears as 3*3 and one of six 8's - as 2*4.
Obviously one can generate infinitely many numbers of this kind. The hard part is to prove that none of them has progenitor, represented in form Pr = 2^i * 3^j * 7^k.
Is there any chance I can get the .py file??
Matt mentioned a theorem that all base 3 numbers after a certain point have a 0 in them. This is demonstrably untrue.
He might have been referring to the theorum that all base 3 powers of 2 have a zero in them, however, and I'm less certain of that one
I'm guessing 77 would be one of the better ones with merely two didgits, right?
77 -> 49
49 -> 36
36 -> 18
18 -> 8
for a total of four steps. I don't imagine you'll easily get a persistence of more than twice the number of digits.
I guess I'll give it the old Parker try.
Ahhhh, the Parker Persistence
Haha a mathematician adding numbers instead of multiplying them.
Done on purpose
@@persereikanen6518 no
Been there done that. In college physics we joked that there was only so much math the brain could hold so the basic stuff was lost. In reality, when you're focused on the complex stuff, making sure you got it right, it's easy to miss that you multiplied 2 by 3 and got 23.
parker maths xD
I think technically he did a multiplication... it was just he reflected that there were four nines, then subconciously kept those two numbers in his brains RAM, and so did the multiplication 4*9, which is obviously equivelant to 9+9+9+9, but I nonetheless do think his brain was in fact multiplying, just it took the wrong numbers as inputs.
why do you convert the steps count to a string before printing it?
Because he's using the + operator which doesn't work on str and int.
What you could do (at least in Python 3, not sure about 2) is: print("TOTAL STEPS", steps)