but tracing it backwards starting from x=N/m (going outwards) until the x value is less than or equal to 1. Note that it is not actually possible for floor(N/phi) and ceiling(N/phi) to both be maximal sequences for the same N; by alternation, one has even length and the other has odd length.
What I found very curious is that, from my calculations, most N have a unique maximal sequence, but for some N, there are actually two maximal sequences. I wasn't able to find any N that had more than two maximal sequences so I'm not sure if they exist (I checked up to N=20000 or so). No, this is not acknowledged anywhere in Riddler's solution, not even in the PDF on the page that gives a list of maximal sequences up to N=200.
There appear to be an infinite number of them but the first few with two maximal sequences as far as I can remember are N=6, 15, 32, 35, ... Considering the Fibonacci fractions 1/1, 2/1, 3/2, 5/3, 8/5, ... mark the boundaries for which values closer to phi give longer sequences, some values of N have two values m1 and m2 where N/m1 and N/m2 both fit in the same "gap". For example, for N=35:
35/23=1.5217...
35/22=1.5909...
Both conveniently fit in the gap between 3/2=1.5 (exclusive) and 8/5=1.6 (inclusive). This gives the two maximal backward sequences (35, 23, 12, 11, 1, 10) and (35, 22, 13, 9, 4, 5). You can check that 35/21=1.6666... is exactly 5/3, so it fits in the gap from 2/1=2 (exclusive) to 5/3=1.6666... (inclusive), a worse gap than 3/2 to 8/5.
I didn't think about it too much, so perhaps there is a proof that an infinite number of N have two maximal sequences, and/or a proof that there is no value of N with more than two maximal sequences, but I probably won't come back to that anymore.
----
As a quick problem, I will present the newest Riddler Express (I will just copy and paste the description):
You have a case with 11 golden globes, weighing 1 kilogram, 2 kg and so on, up to 11 kg. And you know exactly which globe is which.
You have arranged to sell one of the globes to a queen. She has heard tales of these orbs, and knows for a fact that they have masses from 1 kg to 11 kg. However, she doesn’t know which is which and will not simply take your word for it. She will purchase a globe if you can demonstrate its weight.
The queen has a balancing scale with two plates, one on each side. It shows whether the total weight on either plate is equal or, if not, which side is heavier. The queen can clearly see which globes you place on which plate. However, if at any point the mass on either side exceeds 11 kg, the scale will break and the queen will refuse to buy from you.
The queen is in a hurry for her next appointment, so time is limited. What is the fewest number of weighings by which you can prove the weight of at least one globe? Which globe is it?
Answer: Only one weighing required, proves the weight of the 11kg globe. Reasoning: Put 1 2 3 4 on one side and 11 on the other. Four globes on one side weigh a minimum of 10kg. This confirms the lone globe on the other side to be 11kg, since it's the only globe that is possibly heavier than four globes.
This image is an Apollonian gasket, and a very asymmetrical one. I actually used a 3-4-5 triangle where the hypotenuse is in the x axis to generate it. Most importantly, it's generated in a popular fractal generation software called Apophysis. I put the .flame file for the render in GitHub.
The thing is: to my knowledge no one has done that before. The reason is that Apophysis uses an algorithm called IFS to render the fractal, and you actually need to come up with an IFS that will converge to the Apollonian gasket. From what I've seen in the literature, the only cases where an IFS was known were for very symmetrical configurations of the gasket and they actually converged only to a part of it. That's not a problem in most situations, because you can always pick a simple case and transform it to a crazier configuration, but I think that's cheating. I always thought that this limitation of the methods was odd, because my intuition told me that the general case shouldn't be more difficult to solve than the simple ones.
So, after working on this problem on and off for the last week, I can finally say... I DID IT!!!!! Yay, go me. I got an original result.
Anyway, the Github repo I linked before has the code I used, I wrote a Medium article explaining it. I hope it's useful/fun for people here. If you have reached the monthly limit in Medium, reach out to me and I'll send it to you.
(I added numbers to show how long the maximal sequence will be for each interval.)
Alternatively, we can look at the reciprocal fractions 1/1, 1/2, 2/3, 3/5, 5/8, etc. which are the boundaries for the quantity m/N regarding sequence length. The fractions approach 1/phi=0.618...
In order for there to be three or more maximal sequences, there needs to be three separate values m1/N, m2/N, m3/N all in the same interval, and no m/N in any better interval. The situation is shown below, showing the red interval labelled "n" where we want three values, and no value must be in the blue interval labelled ">n". F(n) or Fn means the nth Fibonacci number. (Note: This diagram is for n even. If n is odd, the diagram is reversed so the red interval is below 1/phi, rather than above it. Similar argument.)
Noting that each value m/N is equidistant from each other, it does not appear possible to put three values in the red interval and none in the blue interval. To show this, we just need to show that the red interval is less than twice as long as the blue interval. Or equivalently, the distance from Fn-2/Fn-1 to Fn-3/Fn-2 is less than three times that of the distance from Fn-2/Fn-1 to Fn-1/Fn:
|Fn-2/Fn-1 - Fn-3/Fn-2| = |Fn-22 - Fn-1Fn-3|/(Fn-1Fn-2) = 1/(Fn-1Fn-2)
|Fn-2/Fn-1 - Fn-1/Fn| = |Fn-2Fn - Fn-12|/(Fn-1Fn) = 1/(Fn-1Fn)
where the numerators have absolute value 1 because of Cassini's Identity.
Since Fn is less than three times as large as Fn-2 for n>=5 (note that Fn/Fn-2 tends to phi2 = 2.618...), it follows that 1/(Fn-1Fn-2) is less than three times that of 1/(Fn-1Fn), proving that it is impossible to have three values of m/N in the red interval and none in the blue interval, when n>=5. The cases n=2,3,4 can be ruled out simply by checking exhaustively for N<=6, and observing that for N>=7, there is always a value of m/N in an interval n>=5.
----
Here's the solution. It's based on the concept of a zero-knowledge proof...
See how the color gets weaker the farther we go, that's an intrinsic limitation of the rendering software, but I think it's very cool!
I should write something more elaborate later, but here are the formal properties behind the attractor. You need two Möbius transformations S and T. We take S a diagonal loxodromic transformation, whose multiplier is an ugly complex number you get by solving a quadratic equation with complex coefficients. For T, we take an elliptic transformation that rotates by 120 degrees, so it satisfies T3=I. It also must satisfy another property. An elliptic transformation has two fixed points, and we must choose these fixed points as complex numbers a and b such that their ratio a/b equals an even uglier constant, which is found by multiplying lots of square roots. Once you have these, you construct the two functions in the attractor (notice that my previous approach used four!):
F = ST
G = TS-1
One interesting thing about these generators is that they satisfy (FG)^3 = (GF)^3 = I. You can try proving this if you are bored.
Anyway, if you pick a random Möbius transformation P and conjugate F and G by it, you get another gasket. While it's pretty elegant to generate the transformations like this, it has a drawback, it's pretty impossible to know what the gasket will look like, and you have to input two very complicated constants that, while they do have closed forms, it's much easier to evaluate them numerically. Recently, I've been coding a hybrid of these approaches, where I start with a configuration where I know what the gasket will look like, start changing these transformations, and then modify these constants a little bit. Obviously I don't obtain the Apollonian gasket, but another fractal that still looks cool. The problem is: this is taking a lot of work, which is why I haven't written anything in detail yet, but I should be able to finish soon.
Let me know if you guys find this interesting!This week's Riddler classic is a pretty standard number theory problem. Find a six digit Carmichael number which can be written as ABCABC in base 10. As the Riddler notes, try to solve without writing a brute force code, you learn a lot of number theory doing this.
This week's Riddler classic is a pretty standard number theory problem. Find a six digit Carmichael number which can be written as ABCABC in base 10. As the Riddler notes, try to solve without writing a brute force code, you learn a lot of number theory doing this.
(x-axis is natural numbers and y-axis is the ratio)
(x-axis counts the nth prime and y-axis is the ratio)
Can we prove this ratio tends to zero?
Also beginning with other seed values will generate different sequences. All odd primes will immediately generate 2, so 2 will appear in all such sequences. Are there other primes that appear more often than chance would dictate? Less often?Can we prove this ratio tends to zero?
Now, obviously you have to decide for yourself what 'symbols' means, but after doing that, what's the best you can come up with?
Let c(n) be the count function of operations of the derivative of fn(x). Then c(1)=1, c(2)=7, and
c(n) = n+1+(n-1)+1+3+c(n-1)+n = 3n+4+c(n-1) (assuming I counted operations correctly)
or, in other words, the recursion c(n) - c(n-1) = 3n+4 for all n>=3. Solving this gives a quadratic 1.5n^2+5.5n+C, and with the value c(2)=7, we get c(n)=1.5n^2+5.5n-10 for all n>=2. (Note that as an exception, c(1) doesn't follow this rule because f(2)'s derivative can be simplified to reduce the number of operations, resulting in c(2)=7.)
So this gives quadratic growth with a coefficient of 1.5, the best I can find.
NOTE: The operations f(x)^x ("f(x) to the x") and f(x)^(1/x) ("f(x) root x") also generate three f(x)'s and an f'(x) in their derivatives, but unfortunately their iterations are easily simplified. This disqualifies both of them.
Edit: Added "the derivative of" in there. We're obviously taking the number of operations of the derivative of fn(x), not fn(x) itself.Here's a problem I've been thinking about: ---- You start with a positive number N>1 and want to get down to 1 in a number of moves. Each move consists of going from the current number to a smaller positive number random based on uniform randomness. That is, from k, randomly go to a number 1, 2, ... , k-1 , each with equal probability. Keep doing this until you reach the number 1. For example, starting from 8, a sample three-move sequence is 8→5→2→1: Starting with 8, go from 8→5 (5 is chosen with probability 1/7), then from 5→2 (2 is chosen with probability 1/4), then from 2→1 (1 is chosen with probability 1). Starting from N, what is the expected number of moves to reach the number 1?
You start with a positive number N>1 and want to get down to 1 in a number of moves. Each move consists of going from the current number to a smaller positive number random based on uniform randomness. That is, from k, randomly go to a number 1, 2, ... , k-1 , each with equal probability. Keep doing this until you reach the number 1. ... Starting from N, what is the expected number of moves to reach the number 1?
Finally, the expected number of moves is m(N) / M(N) = N / 2.
I haven't fully digested the content of your post. But I have worked a problem very similar to this with respect to neutron slowing down in my college courses. So I would expect them to have the same answer, which is log_2(N).
