25 Comments
Oct 6, 2023Liked by Zach Wissner-Gross

I think your explanation of the factorial number system may be off by one place. The base 2 digit has a factor of 1!, the base 3 digit has a factor of 2!, etc. Otherwise, you can’t write out odd numbers. https://en.m.wikipedia.org/wiki/Factorial_number_system

Expand full comment
author

Oof. Thanks, Aaron. I think the only part of the puzzle that was wrong was the sample conversion to base 10, which I have updated.

Expand full comment
Oct 6, 2023Liked by Zach Wissner-Gross

Can You Light Up the Pinball Machine

I was hoping to see that someone had derived a closed-form solution for the function E(N), but they haven't. It appears that E(N) has a rational value and I hoped for some insight into this function by examining prime factor ratios that yield the first fourteen values. I discovered a method to calculate the exact probabilities P(N,m) of success on the "m"th pinball flip for any N, but to find E(N) I had to sum the infinite series

E(N) = (1→Inf)∑m*P(N,m)

to a sufficient number of terms and with sufficiently high precision to obtain accurate values of E(N).

Using a computer program with extended-precision (10 byte) floating point variables, I obtained the following decimal values for E(N):

N E(N) Calculated E(N) Actual ???

1 1.000000000000 = 1

2 4.000000000000 = 2²

3 10.000000000000 = 2*5

4 21.333333333333 = 2⁶/3

5 42.666666666667 = 2⁷/3

6 83.200000000000 = 2⁵*13/5

7 161.066666666667 = 2⁴*151/3/5

8 312.076190476190 ≈ 312+2³*11*13*37/5/111111

9 607.085714285714 ≈ 607+3²*11*13*37/5/111111

10 1186.539682539683 ≈ 1186+2*11*13*17*37/3/111111

11 2329.193650793651 ≈ 2329.1+11*13*37*59/2/3/5/111111

12 4588.938528138528 ≈ 4588.9+13*37*89/2/5/111111

13 9067.350072150072 ≈ 9067.3+13*37*347/2/3/5/111111

14 17956.83853923853 ≈ 17956.8+2³*7*31*37/3/5/111111

The values of E(N) for N = 1→7 look like exact values, but then it gets strange. The values of E(N) for N = 8→14 *look* like repeating decimals with a period of six digits. This indicates that if the E(N) were expressed as a rational fraction, there would have to be a factor of 111111 in the denominator of E(N) for all seven values N = 8→14 shown above. That just doesn't seem reasonable to me. What is going to give the prime number 111111? Are these values of E(N) *really* repeating decimals? Does anyone have an explanation for this surprising result?

Expand full comment
Oct 6, 2023Liked by Zach Wissner-Gross

Laurent Lessard's response has an exact form as a finite sum in terms of n. It's

E(n) = Σ Σ (n choose i)/(n–1 choose k–1),

where the sums run from k=1 to n and i=0 to k–1. Your inferred values up to n = 7 are correct, but after that, they are only approximate. The 11111 in the denominator is not real. It's just an artifact of the way you tried to guess at a denominator. The correct values are E(8) = 32768/105, E(9) = 21248/35, E(10) = 74752/63, .... I don't see any particular pattern in the prime factors.

Expand full comment

Thanks for pointing out that Laurent Lessard's exact form for E(N) is a *finite" sum that results in exact (and simple) ratios of integers. I overlooked that solution on my first read.

I still find it interesting that all three of the simple ratios you mentioned in your reply have so many repeated decimal digits:

E(8) = 32768/105 ≈ 312.07619047619...

E(9) = 21248/35 ≈ 607.08571428571...

E(10) = 74752/63 ≈ 1186.5396825396...

In order to see that they are NOT repeating decimals requires computing the infinite sum to an unusually large number of digits, more than my programming language provided.

Expand full comment

They do repeat. 32768/105 = 312.0(761904), 21248/35 = 607.0(857142), and 74752/63 = 1186.(539682), where parentheses surround the repeating part.

Looking again at your expressions, they are correct. 2*11*13*17*37/3/111111 = 34/63. You just failed to cancel some factors, because you thought 111111 was prime.

Expand full comment

Just to close the loop on this topic, here are the results I obtained for E(N), N = 1..14 after substituting 111111 = 3*7*11*13*37 and then canceling like terms in numerator and denominator:

N E(N) Ratio E(N) Prime Factors E(N) Decimal Approx

1 1 = 1 1.00000000000000

2 4 = 4 4.00000000000000

3 10 = 10 10.0000000000000

4 64/3 = 2^6/3 21.3333333333333

5 128/3 = 2^7/3 42.6666666666667

6 416/5 = (2^5*13)/5 83.2000000000000

7 2416/15 = (2^4*151)/(3*5) 161.066666666667

8 32768/105 = (2^15)/(3*5*7) 312.076190476191

9 21248/35 = (2^8*83)/(5*7) 607.085714285714

10 74752/63 = (2^10*73)/(3^2*7) 1186.53968253968

11 733696/315 = (2^9*1433)/(3^2*5*7) 2329.19365079365

12 5300224/1155 = (2^13*647)/(3*5*7*11) 4588.93852813853

13 31418368/3465 = (2^11*23^2*29)/(3^2*5*7*11) 9067.35007215007

14 115552256/6435 = (2^12*28211)/(3^2*5*11*13) 17956.8385392385

Expand full comment

First note: 111111 = 3*7*11*13*37. It's not prime.

Second: I mention the curious factorizations of the numbers in this sequence in my write-up posted on the previous problem (see link below). If we don't drop the integer portion and find the rational for the full value, we get a lot of eerily similar factorizations for every one of the numbers.

I don't think an algebraic closed form solution is likely to exist; the sum of sums (or the output of a Markov chain) is probably the best we can do.

Link: https://drive.google.com/file/d/12Was1kkvsfAEO5-IhnhNGfGfyuDfrzbP/view?usp=sharing

Expand full comment

I found a slightly simpler formula for E(N):

E(N) = N Σ_(k is odd, 1 ≤ k ≤ N) binomial(N, k)/k.

Given this formula, E(N) can be expressed as N (integer)/M!!, where M is the greatest odd number not greater than N.

13!! = 3^3×5×7×11×13, 999999 = 3^3×7×11×13×37, so for N ≤ 14, E(N) can be expressed as (finite decimal)/999999.

For N = 15, 16, 15!! = 3^4×5^2×7×11×13, and since N (integer) above is the multiple of 3, E(N) can be expressed as (finite decimal)/999999.

When N = 17, 17!! = 3^4×5^2×7×11×13×17 and since N (integer) is a multiple of 3×17, E(17) can be expressed as (finite decimal)/999999.

Thus, when N ≤ 17, E(N) repeats decimals in 6-digit cycles. This is because 999999 factors all primes less than 17 except the divisors of 10.

However, when N = 18, E(18) = 4766040064/17017 = 4766040064/(7×11×13×17) has a repetition cycle of more than 6 digits.

Incidentally, E(N) can also be expressed as E(N) = -1/2 N (beta(2, N + 1, 0) + i π), where beta(x, a, b) is the incomplete beta function. This is the analogous continuous expression mentioned in the article.

Expand full comment
Oct 6, 2023Liked by Zach Wissner-Gross

The "making the rounds" problem does not seem very interesting. After swapping x and y (as suggested), I ended up with four quartic equations in 4 unknowns (the small circle radius and the x coordinates of the two intersection points and of the small circle's center). Mathematica will solve these as roots of high-order polynomials (and then give the numerical values), but I didn't find anything simpler.

Expand full comment

My students and I went to our 3D CAD software, used a parametric function for the curve, drew a vertical line, made the unit circle, then made a circle tangent to the 3 shapes. And voila, the answer! While we didn’t do the number crunch, there is something to be said for efficient methods.

Expand full comment

I think the intent is to find a way to do it without having to lean on quartics or Mathematica, i.e., as if it were a contest math problem. That makes it more interesting. I think I've come close but haven't quite gotten there yet.

Expand full comment
Oct 7, 2023·edited Oct 7, 2023Liked by Zach Wissner-Gross

Fiddling around (hah!) a little more with Mathematica, I was able to show that the radius r is the unique real solution of the cubic equation

8r^3 + 24r^2 + 74r - 17 = 0.

You can then use the cubic formula to get a closed-form answer. That's as simple as it gets.

Expand full comment

I decided to take a shot at deriving this cubic equation. I solved for the intersection of the locus of points equidistant from the x axis and the big circle with the locus of points equidistant from the x axis and the parabola. Here's what I got:

For each value of u along the parabola (u,u²) there is a point along the normal to the parabola where the length of the normal is equal to its y coordinate. The (x,y) coordinates of this point can be calculated as follows:

Let a = u²

Let b = √(1+4a)

Let y = a/(1+1/b) (1)

Let x = u+2u(a-y) (2)

The solution is where the above locus intersects y = (1-x²)/2, x = √(1-2y) (3)

The three equations above, in three unknowns, x, y, and u, should allow a solution for all three unknowns.

Eliminate x from the equations:

x = √(1-2y) = u+2u(a-y)

Eliminate u by solving y = a/(1+1/b) for a:

y(b+1) = ab

y[√(1+4a) + 1] = a√(1+4a)

y = (a-y)√(1+4a)

√(1+4a) = y/(a-y)

1+4a = y²/(a-y)²

(1+4a)(a²-2ay+y²) = y²

a²-2ay+y²+4a³-8a²y+4ay² = y²

Fortunately the y² cancels out =>

a[4a²+(1-8y)a+2(2y²-y)] = 0

Divide out the extraneous root a=0, leaving a quadratic

4a²+(1-8y)a+2y(2y-1) = 0

with roots a = {(8y-1)±√[(8y-1)²+32y(1-2y)]}/8

a = {(8y-1)±√[16y+1]}/8

Check this result using the known value of y:

y 0.213841779235356

a 0.351682881060849

u 0.593028566816851

That is the correct value of u so it checks.

Equations (2) and (3) give x² = 1-2y = {u[1+2(a-y)]}²

1-2y = a[1+4(a-y)+4(a-y)²]

Substituting the a derived from (1) gives the equation to be solved for y.

Let c = √[16y+1]

Looking at the pieces...

(a-y) = [c-1]/8

(a-y)² = [8y+1-c]/32

4(a-y)+4(a-y)² = y+3{c-1}/8

1+4(a-y)+4(a-y)² = y+5/8+(3c/8)

1-2y = {(8y-1)+c}{8y+5+3c}/64

The next step is to collect the terms with c on one side of the equal and square, etc.

After a good bit of tedious but routine algebra, this intermediate step appears:

(16y+1)³ = (33-104y-32y²)²

(This checks out with MarkS' solution, giving 86.43698231797 for both sides of the equal.)

After expanding the powers and more tedious algebra, I got

16y⁴ + 40y³ + 124y² - 108y + 17 = 0 <====================

So this is not the cubic equation found by MarkS. What happened?

There is an extraneous root y = 1/2. I can divide it out using synthetic division:

(8y³ + 24y² + 74y - 17) * (2y - 1) = 0 <====================

And there it is, the solution found by MarkS.

This is pretty tedious. I was interested in the claim that this was an interview question, and I don't think it is necessarily a bad one if the intent of the examiner is to see how the candidate thinks about such problems. Such interviews aren't graded pass-fail depending on whether they arrive at the answer. A way of getting the answer, much simpler than the above, is successive approximation, and I have shown that the convergence can be quite fast. I think a candidate would get "points" for coming up with the equation for points equidistant from the x axis and the big circle, and more points for the equation for points equidistant from the x axis and the parabola, etc.

Expand full comment

Making the Rounds

Rapidly Converging Successive Approximation

This is the rapidly converging successive approximation I wanted, but I didn't think of it until now. The setup is the same as I described in the previous post, resulting in the point (u,u²) on the parabola where the normal to the parabola (with slope m = -1/2u) passes through the initial guess (x,y) = (1,0). That resulted in the initial value of u = 0.589754512301459. Successive solutions are obtained from the successive values of u.

The procedure is to project the normal passing through (u,u²) to a point where its length is equal to its y coordinate. That gives a new value for y, and then the new value for x is √(1-2y). Then this (x,y) is used to determine the next u.

Repeat:

1. Let a = u²

2. Let b = √(1+4a)

3. Let y = a/(1+1/b)

4. Let x = √(1-2y)

5. Let u = u - (2u³+ (1-2y)u - x)/(6u² + 1-2y)

6. Go to 1.

Some results are shown below. Note that the very first iteration gives a y value that is off by only 0.0026.

Iter u y = a/(1+1/b) x = √(1-2y) u = u -(2u³+ (1-2y)u-x)/(6u²+ 1-2y) Error

1 0.589754512 0.211219391 0.759974485 0.593173512 -0.002622388

2 0.593173512 0.213958303 0.756361946 0.593022692 0.000116524

3 0.593022692 0.213837057 0.756522231 0.593028806 -4.72229E-06

4 0.593028806 0.213841971 0.756515735 0.593028557 1.92184E-07

5 0.593028557 0.213841771 0.756515999 0.593028567 -7.82003E-09

6 0.593028567 0.21384178 0.756515989 0.593028567 3.18201E-10

7 0.593028567 0.213841779 0.756515989 0.593028567 -1.29481E-11

8 0.593028567 0.213841779 0.756515989 0.593028567 5.26468E-13

9 0.593028567 0.213841779 0.756515989 0.593028567 -2.17604E-14

10 0.593028567 0.213841779 0.756515989 0.593028567 5.82867E-16

Expand full comment

Very impressive result! I decided to crunch the numbers just to see it work:

My first step was to get the unique real solution to the cubic using Newton's Method.

I got y = 0.213841779235356 <=================

The locus of points equidistant from the circle and the x axis is easily found. It is

y = (1-x²)/2, or x = √(1-2y).

That gives x = 0.753623607729932

I took the given advice and swapped x and y in the original problem. Now I have a parabola y = x² instead of the square root. The points along this parabola are (u,u²) and the slope m of the normal to the parabola at (u,u²) is -1/2u.

So, (y-u²) = (-1/2u)*(x-u), or 2u³ + (1-2y)u - x = 0.

Another cubic, with solution u = 0.593028566816851

So the point of tangency with the parabola is (u,u²) = (0.593028566816851, 0.351682881060848)

And now, the distance from (x,y) to (u,u²) is √[(x-u)²+(y-u²)²] = 0.213841779235355

So, it checks out and the circle really is centered at (x,y) = (0.753623607729932, 0.213841779235356) with radius r = y.

Expand full comment

Correction to the number crunch previously posted. An incorrect number is shown for x in my original post, but I never actually used that number in the verification so the rest of the calculation is correct. The correct value of x is

x = √(1-2y) = 0.756515988944905 (not 0.753623607729932).

That means the coordinates of the center of the small circle are actually

(x, y) = (0.756515988944905, 0.213841779235356)

Expand full comment

Very nice though! That would see to move it out of the realm of contest math, unless the answer "real root of P(x)" would be valid on such tests.

Expand full comment

Assuming this really was an oral exam problem, I am pretty sure I would not have been able to come up with an algebraic solution like that found by MarkS. Instead, I would propose a method of successive approximation that starts with a (bad) guess at the answer and proceeds to refine it in a method analogous to Newton's Method. I would describe the following steps and suggest that if they were carried out repetitively they would converge to the solution.

Setup:

1. Transpose x and y axes as suggested so as to give a parabola y = x² rather than the original y = √x

2. It is a simple matter to find the locus of points equidistant from the big circle and the x-axis: y = (1-x²)/2, or x = √(1-2y). The center of the smaller circle must lie somewhere along this curve.

3. Decide on an initial (bad) guess for the position of the center of the circle. I choose (x,y) = (1,0).

4. Calculate an initial point of tangency of the circle with the parabola y = x²:

(y-u²) = (-1/2u)(x-u)

-u² = (-1/2u)(1-u)

2u³ = 1-u

2u³ + u - 1 = 0

Newton's Method => u = 0.589754512301459, (u,u²) = (0.589754512301459,0.347810384779931)

Repeat:

1. Calculate the perpendicular distance from (x,y) to (u,u²) as follows:

s = √[(x-u)²+(y-u²)²]

2. Calculate the next approximation to y as (s+y)/2. Note that this is a key step because it is EXACTLY TRUE when (x,y) is the correct solution but only approximately true otherwise.

3. Calculate the corresponding new x as x = √(1-2y)

4. Calculate a new u from 2u³ + (1-2y)u - x = 0 using ONE STEP of Newton's Method with the previous u as the starting value:

5. New u = u - (2u³ + (1-2y)u - x) / (6u² + 1 - 2y)

6. Display current value of y.

7. Go to 1.

I wrote this algorithm in a spreadsheet and found that it does converge to the root of the cubic provided by MarkS, although not as rapidly as I would have liked. Here are the results, omitting the calculations of the intermediate values of u, s, x, and y. The Error column is the difference between my calculated r value and the value obtained from MarkS' cubic.

Iter y = r Error

0 0 -0.213841779

1 0.268920724 0.055078945

2 0.194319186 -0.019522593

3 0.220074697 0.006232918

4 0.211782636 -0.002059143

5 0.214514474 0.000672694

6 0.213621211 -0.000220568

7 0.213914014 7.22345E-05

8 0.213818114 -2.36656E-05

9 0.213849532 7.75238E-06

10 0.21383924 -2.53963E-06

11 0.213842611 8.31956E-07

12 0.213841507 -2.72541E-07

13 0.213841869 8.92819E-08

14 0.21384175 -2.92479E-08

15 0.213841789 9.58132E-09

16 0.213841776 -3.13875E-09

17 0.21384178 1.02822E-09

18 0.213841779 -3.36837E-10

19 0.213841779 1.10344E-10

20 0.213841779 -3.61481E-11

21 0.213841779 1.18413E-11

22 0.213841779 -3.87956E-12

23 0.213841779 1.27046E-12

24 0.213841779 -4.16639E-13

25 0.213841779 1.36058E-13

26 0.213841779 -4.50473E-14

27 0.213841779 1.43219E-14

28 0.213841779 -5.13478E-15

29 0.213841779 1.19349E-15

30 0.213841779 -8.32667E-16

31 0.213841779 0

Expand full comment

If it were actually an interview question, I think this might be the sort of thing you'd want to do. That said, why start with a bad guess when you can guess (0.75, 0.2187) or (0.8, 0.18) just based on the picture?

Expand full comment

I am assuming that divisible means that that the Factorial number is converted to base 10, than divided and the remainder must be zero. Maybe that is obvious to most, but I am a little unsure.

Expand full comment
founding

That’s one way to look at it, but keep in mind that divisibility doesn’t depend on the way the numbers are represented. Only the shortcuts we use depend on the base. So, a decimal number is divisible by ten if it ends in zero, but that rule doesn’t work in binary: four is written 100, but is still definitely not divisible by 10.

When the problem asks about divisibility by 1 through 9, each of those is understood to be in base 10. (None of them would be valid factorial numbers anyway, since they don’t end in 0.)

Expand full comment

Just a warning: The example is wrong. As stated, "the place value of the Nth digit is (N−1)!." But then in the example, 103210 is interpretted as 1(6!) + 0(5!) + 3(4!) + 2(3!) + 1(2!) + 0(1!), or 806. It should be 1(5!) + 0(4!) + 3(3!) + 2(2!) + 1(1!) + 0(0!), or 143

Expand full comment
author

Hey, Joe. Thanks -- I corrected that earlier this morning.

Expand full comment