numbers – MathematRec

Two, three, four

23 August 202023 August 2020 by Rich Holmes, posted in Numbers, Uncategorized

Last year was a big year for the sum of three cubes problem, which asks whether all numbers not of the form $9k+4$ or $9k+5$ can be written as the sum of the cubes of three (positive, negative, or zero) integers, $a^3+b^3+c^3$ . It’s a hard problem. The smallest solution for 42 is

$42 = (-80\ 538\ 738\ 812\ 075\ 974)^3 + 80\ 435\ 758\ 145\ 817\ 515^3 + 12\ 602\ 123\ 297\ 335\ 631^3$

A superficially similar problem is to find ways to write an integer $N$ as the sum of a square, a cube, and a fourth power: $N = a^2+b^3+c^4$ . As with the three cubes problem, we allow $b$ to be negative, though obviously there’s nothing to be gained by considering negative values for $a$ or $c$ .

It’s not at all obvious all numbers can be so written, or that they can’t, or which numbers can’t if there are any, or whether it’s harder or easier to find such representations than it is to find sums of three cubes. Of course any number that is itself a square, cube, or fourth power has a solution using zero for the other two powers, and any number that is one or two more than a square, a cube, or a fourth power is trivial as well, as is any number that is one less than a square or a fourth power. And compared to the three cubes problem, the search space here is in some sense smaller since we require $0 \le a^2 \le (N-b^3)$ and $0 \le c^4 \le (N-b^3)$ .

In fact all positive numbers up to 100 except for one have solutions with relatively small numbers: the worst of them, in the sense of having a large minimum value for $W = a^2+|b|^3+c^4$ , is $75 = 171^2+(-31)^3+5^4$ . The exception is this one:

$67 = (213\ 662)^2+(-6\ 337)^3+676^4$

It’s reminiscent of the three cubes problem in that you have this much harder number embedded among much easier ones. But it’s nowhere near as hard as 42 as a sum of three cubes.

For the numbers -10 000 through 10 000 a brute force Python script quickly turns up solutions for all. The one with largest $W$ (3 times the next largest) is $-8\ 357 = (3\ 303\ 433)^2 + (-22\ 183)^3 + 239^4$ .

Is there a proof all numbers have solutions? Maybe. There is an easy (to follow) proof that every integer is a sum of two squares and a cube of an integer, and a proof (paywalled) that almost all positive integers are sums of a square, a positive cube, and a fourth power. Not having shelled out to read it — the paper’s ten pages long, so I infer it’s not an easy proof — I don’t know if it identifies all the exceptions; if it does, then finding solutions with negative $b$ for those would prove our puzzle for positive $N$ . In 71 years you’d think it would have been done by now, and perhaps extended to negative $N$ , and maybe it has. But that’s all I’ve found so far. Finally, for expressing $N$ as $a^2+b^3+c^3$ , this paper reports no proof but there are solutions for all $-4\ 000\ 000 \le N \le 2\ 000\ 000$ .

Take Away Triangles

1 July 20202 July 2020 by Rich Holmes, posted in Numbers

Matt Parker calls his latest puzzle Take Away Triangles, though really it has nothing to do with geometry; it’s purely about numbers.

Consider a triple of integers (Parker doesn’t say they have to be positive, but he doesn’t say they don’t): $(a, b, c)$ . Without loss of generality, herein I’m going to require all such triples to be in nondecreasing order: $a \le b \le c$ . Now make a new triple out of it using the three differences $b-a$ , $c-b$ , and $c-a$ . These all are nonnegative, and of them $c-a$ is the largest (in fact $c-a = (b-a) + (c-b)$ ), so the new triple is either $(b-a, c-b, c-a)$ or $(c-b, b-a, c-a)$ . We’ll call this new triple the successor of the first, and the first is a predecessor of the second. Now of course we can find the successor of the successor, and the successor of the successor of the successor, and so on.

For instance, starting with $(5, 7, 12)$ , we get as its successors $(2, 5, 7)$ , then $(2, 3, 5)$ , then $(1, 2, 3)$ , and so on.

The basic puzzle is this: Find a triple whose members do not sum to 14, whose successor does sum to 14, as do all the successors in the chain after that.

Let’s approach this in three steps:

Find all triples that do sum to 14 whose successor also sums to 14
Identify all whose second and following successors also sum to 14
Find all predecessors of those triples

All right. We want to find a triple $(a, b, c)$ such that $a+b+c = 2s$ ( $s$ is 7, but let’s keep it symbolic for now, and you’ll see why I put a factor of 2 there). Its successor has members $b-a$ , $c-b$ , and $c-a$ , and we want them to sum to $2s$ too: $b-a+c-b+c-a = 2c-2a = 2s$ , so $c-a = s$ or $a = c-s$ . We have $b = 2s - a - c = 2s-(c-s)-c = 3s-2c$ . So triples of the form $(c-s, 3s-2c, c)$ will work.

What values can we use for $c$ ? We need $a \le b$ so $c-s \le 3s-2c \implies c \le 4s/3$ , and $b \le c$ so $3s-2c \le c \implies c \ge s$ . For $s=7$ that means $7 \le c \le 9$ . The only triples that sum to 14 whose successors also sum to 14 are:

$(0, 7, 7)$ , whose successor is $(0, 7, 7)$
$(1, 5, 8)$ , whose successor is $(3, 4, 7)$
$(2, 3, 9)$ , whose successor is $(1, 6, 7)$

Next step is easy. The second and third of these have second successors which do not sum to 14. The first is its own successor, and therefore all of its successors: It and all its successors sum to 14, and that’s the only triple with that property.

Now we just need a predecessor for $(0, 7, 7)$ , or better yet, all predecessors. Any that don’t sum to 14 will answer the puzzle. So we want $(e, f, g)$ such that either

$f-e = 0$
$g-f = 7$ and
$g-e = 7$

$f-e = 7$
$g-f = 0$ and
$g-e = 7$

In the first case, $e=f$ and $f = g-7$ so we have predecessors of the form $(g-7, g-7, g)$ . The second case works out to $(g-7, g, g)$ . So predecessors of the first kind include $(-2, -2, 5), (-1, -1, 6), (0, 0, 7), (1, 1, 8),$ and $(2, 2, 9)$ . Predecessors of the second kind include $(-2, 5, 5), (-1, 6, 6), (0, 7, 7), (1, 8, 8),$ and $(2, 9, 9)$ . Only $(0, 7, 7)$ sums to 14. Any other triple of one of these forms solves the puzzle.

Now let’s consider some wider aspects.

First, given a triple $(a, b, c)$ with $a, b, c \ge 0$ , what are its predecessors? We want $(e, f, g)$ such that either

$f-e = a$
$g-f = b$ and
$g-e = c$

$g-f = a$
$f-e = b$ and
$g-e = c$

In either case, $a+b$ must equal $c$ , so only triples for which that is true have predecessors. Then in the first case: $f = a+e$ , $g = b+f = a+b+e = c+e$ , and $e$ is unconstrained, so the predecessors are $(e, a+e, c+e)$ for all $e$ . In the second case we get $(e, b+e, c+e)$ .

Second, given a starting triple, what’s the behavior of its successors? Can they go indefinitely without repeating? If they do repeat, what’s the period of the repetition?

A triple that is the successor of another triple must be of the form $(x, y, x+y)$ . The successor of that successor must be either $((y-x), (x+y)-y, (x+y)-x)$ or $((x+y)-y, (y-x), (x+y)-x)$ . But these simplify to $(y-x, x, y)$ or $(x, y-x, y)$ . In either case two of the second successor’s members are the first two members of the first successor. In particular, the third member of the second successor is the second member of the first successor.

What that means is the chain cannot continue indefinitely without repeating, because the third member cannot increase (except in the successor to the starting triple, and that only if the starting triple’s first member is negative). It’s bounded from above in all successors by its value in the starting triple’s successor and from below by zero, and the first and second members must be no larger and nonnegative, so there is only a finite number of triples that can occur in the successor chain, and eventually it must repeat.

We’ve seen the repetition period can be 1. If that is the case — if we reach a triple $(x, y, x+y)$ which is its own successor — then the third member of its successor, $(x+y)-x = y$ , must be equal to $x+y$ implying $x = 0$ . So the only self-succeeding triples are of the form $(0, y, y)$ .

Can the period be longer? The largest member cannot increase, so if it is $x+y$ in the first triple in the repeating cycle and is to be $x+y$ in some later triple in the cycle, it must be $x+y$ in every triple in the cycle. In particular it must be $x+y$ in the successor to the first triple of the cycle, so again $x=0$ , the cycle’s first triple must be $(0, y, y)$ , and that is self-succeeding. So the period must be 1.

For any starting triple, then, the chain of successors after a finite number of steps reaches a triple of the form $(0, y, y)$ and repeats that triple from there on.

Skew your Legos

30 July 2019 by Rich Holmes, posted in Numbers

The Lego architecture photo blog Archbrick Daily recently featured this Micropolis City Swim Center by Little Brick Root:

Unusually for a Lego model (or for a real world building, for that matter) the structure is at an angle relative to the base. Of course you can do that sort of thing by covering the base with flat tiles, except for one single stud:

Then the structure can be at any angle, rotating around that stud. For that matter you could cover the entire base with flat tiles and just put the structure on top in any position or orientation, but that’s rather susceptible to jostling, isn’t it? So is the single stud connection, though less so.

(There also are Lego pieces with built in angles, such as this one:

But let’s just consider normal rectilinear bricks and plates for now.)

But maybe you want a rigid connection. If you happen to want an angle of, oh, I don’t know, let’s say 36.87°, you can do that, Make a base with two studs three rows and four columns apart:

The distance in stud units between the two studs is $\sqrt{3^2+4^2}=5$ , an integer, so for instance a 1 by 6 brick can be placed on the two studs. If you want other angles you can look for other primitive Pythagorean triples to use. (Primitive meaning it’s not just another triple scaled up: (6, 8, 10), for instance, is a triple, but it’s just twice (3, 4, 5), and makes the same angle.)

The angles you get have rational values for their sine, cosine, and tangent. If you want 45°, you’re out of luck; sin(45°) is irrational. You can get pretty close, though, with for instance the triple (20, 21, 29). That gives an angle of 43.60°.

But if you want a small angle, like the Swim Center model, what do you do? Another way to think about it is, you want a triangle where the long side is nearly as long as the hypotenuse. With Pythagorean triples, the best you can get is a hypotenuse 1 unit longer than the long side.

A general formula for triples is $a=v^2-u^2, b=2uv, c=v^2+u^2$ where $u$ and $v>u$ are coprime and opposite parity (one even, one odd). Here obviously the smallest difference between $a$ and $c$ is 2, so we want $c-b = 1 = v^2+u^2-2uv = (v-u)^2$ . So $v=u+1$ and $a=2u+1, b=2u^2+2u, c=2u^2+2u+1$ . The first several of these are:

u	a	b	c	angle
1	3	4	5	36.87°
2	5	12	13	22.62°
3	7	24	25	16.26°
4	9	40	41	12.68°

You can see you have to make a fairly large model if you want a rigid angle of less than 10° — more than 40 studs wide, if you use conventional plates and bricks. There are “jumper” plates, though, that give access to half integer spacing, meaning you’d need only half the width.

You can get smaller angles by stacking triples. For instance, you can mount a plate at 36.87° to the base using (3, 4, 5), then mount a plate to that at -16.26° using (7, 24, 25), then mount a plate on top of that also at -16.26° giving a net angle of 4.35°. The stacked plates can hide inside the structure so all you see is the base and the structure rotated 4.35°.

The ground floor of the Swim Center is 24 studs wide, meaning the largest distance between stud receivers is 46 half studs, accommodating no triples with angles smaller than 12.68°. The actual angle of the model is about 5°. So maybe Little Brick Root used angled Lego pieces (I don’t know of any with that small an angle, but maybe) or stacked triples, or maybe (mostly likely is my guess) only a single stud connection to the base. But not a rigid connection based on a single triple, that’s for sure.

Sum ideas (part 4)

22 June 201919 June 2019 by Rich Holmes, posted in Numbers

So how do you sum — or, if you prefer, associate a value with — $1+1+1+...$ ?

One way is zeta function regularization. For this we start with the sum

$\displaystyle S(s) = \sum_{k=1}^{\infty}k^{-s}$ .

For example, $S(2) = 1+1/4+1/9+1/16+...$ . This series converges to the limit $\pi^2/6$ . In fact $S(s)$ converges for any complex $s$ where the real part $\Re(s) > 1$ .

For $s=1$ , $S(1) = 1+1/2+1/3+1/4...$ and this diverges. If you approach $s=1$ along the real axis you find $S(s)$ increases without limit. Off the real axis, things are a little different. At $s=1+i$ , for example, the sum fails to converge, but as you approach t $s=1+i$ from the right, $S(s)$ approaches $0.58215 + 0.92684i$ . Similar behavior is found elsewhere on the $\Re(s) = 1$ line, other than $s=1$ .

That suggests there might be a way to construct a function that is equal to $S(s)$ for $\Re(s)>1$ but which has well defined values elsewhere, except $s=1$ . And indeed there is: analytic continuation.

Imagine I give you the following function: $f(x) = x$ for real $x \in [0,1]$ . Outside that interval $f(x)$ is undefined. But you obviously could define another function $g(x) = x$ which is defined on the whole real number line and has the property that $g(x) = f(x)$ in the range where $f(x)$ is defined. Obviously $g(x)$ is continuous, and is differentiable everywhere.

On the other hand, you could instead define $g(x)$ as being quadratics grafted onto the line from $(0,0)$ to $(1,1)$ :

$g(x) = x^2+x \quad x < 0$
$= x \quad 0 \le x \le 1$
$= x^2-x+1 \quad x > 1$

which has the same properties. Or you could use cubics, or quartics, or, well, anything provided it has the right value and derivative at $0$ and $1$ . There’s an infinite number of ways to continue $f(x)$ to the entire real line.

In the complex plane you can do something similar. I give you a function $f(z)$ defined for $z$ within some region of the complex plane. $f(z)$ is analytic, that is, it has a complex derivative everywhere it’s defined. Then you can give me an analytic function $g(z)$ defined everywhere in the complex plane and equal to $f(z)$ everywhere $f(z)$ is defined. (I’m being sloppy and informal here; there could be poles where neither function is defined, for example.)

Here’s the thing, though: Unlike $g(x)$ on the real line, $g(z)$ is unique. There is exactly one analytic function that continues my analytic function to the entire complex plane.

So, getting back to our sum (which is analytic), we can define an analytic function $\zeta(s) = S(s)$ for $\Re(s) > 1$ , whose behavior for $\Re(s) \le 1$ is given by analytic continuation. One can show

$\displaystyle \zeta(s) = \frac{1}{\Gamma(s)}\int_0^\infty \frac{x^{s-1}}{e^x-1} dx$

where $\Gamma(s) = \int_0^\infty x^{s-1}e^{-x} dx$ is the usual gamma function. $\zeta(s)$ has a pole at $s=1$ but is well defined everywhere else. $\zeta(s)$ is known as the Riemann zeta function.

Now, we know $\zeta(s)$ is the value of $\sum_{k=1}^{\infty}k^{-s}$ wherever that sum converges. Zeta regularization just assigns the value of $\zeta(s)$ to that sum where it does not converge as well. For instance, when $s=0$ , we have $1+1+1+1+... = \zeta(0)$ , and $\zeta(0) = -1/2$ .

The somewhat notorious sum of the positive integers, $1+2+3+4+...$ , is $S(-1)$ , to which is assigned the value $\zeta(-1) = -1/12$ . If you want to start an argument on the Internet, claiming that $1+2+3+4+... = -1/12$ is a good way to do it. Of course that claim glosses over a lot.

It turns out the negative even integers are (“trivial”) zeros of the zeta function, so $\sum_{k=1}^{\infty}k^{2n} = 0$ by this summation method. Generally, for integer exponents,

$\displaystyle \sum_{k=1}^{\infty}k^{n} = \zeta(-n) = (-1)^n \frac{B_{n+1}}{n+1}$ ,

where $B_n$ is the nth Bernoulli number,

$\displaystyle B_n = \sum_{k=0}^n\sum_{v=0}^k (-1)^v\binom{k}{v}\frac{v^m}{k+1}$ .

$\displaystyle \sum_{k=1}^{\infty}k^{1} = -\frac{1}{12}$
$\displaystyle \sum_{k=1}^{\infty}k^{3} = \frac{1}{120}$
$\displaystyle \sum_{k=1}^{\infty}k^{5} = -\frac{1}{252}$
$\displaystyle \sum_{k=1}^{\infty}k^{7} = \frac{1}{240}$
$\displaystyle \sum_{k=1}^{\infty}k^{9} = -\frac{1}{132}$
$\displaystyle \sum_{k=1}^{\infty}k^{11} = \frac{691}{32760}$

and on from there.

Sum ideas (part 3)

20 June 201919 June 2019 by Rich Holmes, posted in Numbers

Another summation method is Abel summation. The idea is, if we have

$\displaystyle S = \sum_{k=0}^{\infty} a_k$

then we can define

$\displaystyle f(r) = \sum_{k=0}^{\infty} a_kr^{k}$

for $r \in [0, 1)$ . Then if $\lim_{r\to 1^-} f(r)$ exists and is finite, that limit is the Abel sum of $S$ .

As a simple example, apply this to Grandi’s series, $1 - 1 + 1 - 1 ...$ . Here $f(r) = 1 - r + r^2 - r^3 ... = 1/(1+r)$ for $|r|<1$ . The limit as $r\to 1$ is $1/2$ , the same result as we obtained using Cesàro summation. In fact it can be shown that Abel summation is stronger than Cesàro summation, i.e., for series that can be Cesàro summed, Abel summation give the same result, but there are additional series which can be Abel summed but not Cesàro summed. Of course Cesàro summation is consistent with ordinary summation for convergent series, and therefore so is Abel summation: that is, Abel summation is regular.

Here’s another example. Consider

$\displaystyle 1-2+3-4+... = \sum_{k=0}^{\infty} (-1)^k(k+1)$ .

Not only does this series not converge, but the partial sum averages don’t converge either, so it is not Cesàro summable. But it is Abel summable. We make this sum into a function

$\displaystyle f(r) = \sum_{k=0}^{\infty} (-1)^k(k+1)r^k = r^0-2r^1+3r^2-4r^5...$

But now notice: $r^0 = -d(-r)^1/dr$ , $-2r^1 = -d(-r)^2/dr$ , $3r^2 = -d(-r)^3/dr$ , and so on:

$\displaystyle f(r) = -\frac{d}{dr}\sum_{k=0}^{\infty} (-r)^k$

and, again, for $|r|<1$ ,

$\displaystyle f(r) = -\frac{d}{dr}\frac{1}{1+r} = \frac{1}{(1+r)^2}.$

Now the Abel sum is $\lim_{r\to1^-} f(r) = 1/4$ .

A couple more properties (besides regularity) a summation method might have are linearity and stability. For the following let $\mathbf {A}(r)$ denote the result of applying summation method $\mathbf {A}$ to series $r$ . By linearity is meant: if $\mathbf {A}(\sum a_n) = s$ and $\mathbf {A}(\sum b_n) = t$ then $\mathbf {A}(\sum ka_n+b_n) = ks+t$ . By stability is meant: if $\mathbf {A}(a_0+a_1+a_2+...) = s$ then $\mathbf {A}(a_1+a_2+...) = s-a_0$ , and conversely. Cesàro summation and Abel summation both are linear and stable. So is classical summation, for that matter.

You can prove that for any linear and stable summation method $\mathbf{A}$ , the sum of the Grandi series $\mathbf{A}(g)$ is $1/2$ , if that sum exists:

$\mathbf{A}(g) = \mathbf{A}(1-1+1-1+1...) = 1 + \mathbf{A}(-1+1-1+1...)$ (by stability)
$= 1 - \mathbf{A}(1-1+1-1...)$ (by linearity)
$= 1 - \mathbf{A}(g)$ and so
$\mathbf{A}(g) = 1/2$ .

That “if that sum exists” provision is important. For instance, classical summation of the Grandi series is undefined, not $1/2$ , even though classical summation is linear and stable. You can come up with similar proofs about linear and stable sums of other series, that they must always have some particular value if they have a value at all. Showing that they do indeed have a value is another matter!

Conversely, you can prove some series do not have values for any summation method that is linear and/or stable. For example, suppose $\mathbf{A}$ is stable and $\mathbf{A}(\sum_{k=0}^\infty 1)$ has value $a$ . Then

$a = \mathbf{A}(1+1+1+1+1...) = 1 + \mathbf{A}(1+1+1+1...)$ (by stability)
$a = 1 + a$ ,

an impossibility. So $\sum_{k=0}^\infty 1$ cannot be summed by any stable summation method. There are unstable methods, however, that can sum that series.

Sum ideas (part 2)

19 June 201920 September 2019 by Rich Holmes, posted in Numbers

So, what about divergent series?

A divergent series has no limit, so we can’t assign that as a value. Conventionally we just say it has no value, its value is undefined. But in fact some divergent series can be associated with a definite quantity by means other than the limit of the sequence of partial sums. For some purposes, it can be useful to regard that quantity as the value, or a value, of the series.

There are lots of ways to associate a value with a divergent series; lots of summation methods, as they are called. It’s unfortunate terminology, in that it suggests they’re methods for finding the unfindable sum of the infinite number of numbers. But it’s the terminology we’re stuck with.

Summation methods are kind of like technical standards: the great thing about them is there’s so many to choose from. Generally a given summation method can be used with some series, but not with others. Some methods are stronger than others, in the sense that the one can be applied to any series the other can, with the same result, but it can also be applied to some series the other can’t handle.

Perhaps the simplest summation method applicable to a divergent series is Cesàro summation. In its simplest form, this is just finding the limit not of the partial sums of a series, but the average of the partial sums. For example, Grandi’s series is

$1 - 1 + 1 - 1 + 1 - 1 + ...$ .

The first partial sum is $1$ , the second is $1-1=0$ , the third is $1-1+1=1$ , the fourth is $1-1+1-1=0$ , and so on — they alternate between $1$ and $0$ . They don’t converge. But the average of the first one partial sum is $1$ , the average of the first two is $1/2$ , the average of the first three is $2/3$ , the average of the first four is $1/2$ , and so on, forming the sequence

$\displaystyle 1, \frac{1}{2}, \frac{2}{3}, \frac{1}{2}, \frac{3}{5}, \frac{1}{2}, \frac{4}{7}, \frac{1}{2}...$

and that sequence does converge, to $1/2$ . This value is the Cesàro summation of Grandi’s series.

Now, we know if we add together a finite number of integers, we get an integer, and it seems crazy to think you could sit down and add an infinite number of integers and get a fraction. Then again, it’s crazy to think you could sit down and add an infinite number of integers. And that’s not what we’re doing. But we know the partial sums alternate between $0$ and $1$ , so the value halfway between, $1/2$ , in some sense does characterize the behavior of the infinite series.

A reasonable question to ask is, what’s the Cesàro summation of a convergent series? It doesn’t take too much thinking to realize intuitively that if a series converges, then the average of the partial sums also should converge and to the same value. For instance, the partial sums of

$S = \displaystyle \sum_{k=0}^{\infty} \frac{1}{k!}$

converge to $e$ , and so do the averages of the partial sums. Granted, the partial sums converge much faster: after just 12 terms the partial sum is $2.718281828...$ while after 10000 terms the average of the partial sums is still $2.717281831...$ . But it’s getting there. A summation method that gives the conventional limit when applied to a convergent series is called regular. Cesàro summation is regular, and clearly that’s a nice attribute to have: it means Cesàro summation is consistent with ordinary summation, but is stronger in the sense that it also gives results for some series which have no classical value.

But does it make sense to say

$\displaystyle 1 - 1 + 1 - 1 + 1 - 1 + ... = \frac{1}{2}$ ?

It’s an unconventional and probably misleading use of the equal sign, but if it’s understood you’re talking about a value assigned using a summation method, specifically Cesàro summation, you maybe can get away with it. But you can also make the sense more explicit. Hardy again:

We shall make systematic use of the following notations. If we define the sum of $\Sigma a_n$ , in some new sense, say the ‘Pickwickian’ sense, as $s$ , we shall say that $\Sigma a_n$ is summable (P), call $s$ the P sum of $\Sigma a_n$ , and write

$\Sigma a_n = s$ (P).

We shall also say that $s$ is the P limit of the partial sum $s_n$ , and write

$s_n \to s$ (P).

Sum ideas (part 1)

19 June 201919 June 2019 by Rich Holmes, posted in Numbers

[I]t is broadly true to say that mathematicians before Cauchy asked not “How shall we define 1 – 1 + 1 – …?” but “What is 1 – 1 + 1 – …?”, and that this habit of mind led them into unnecessary perplexities and controversies which were often really verbal.
— G. H. Hardy, Divergent Series

What is the value of an infinite series?

I mean, what does “value” mean here?

With a finite series, you can (in principle) just add all the numbers together. You take the result and call that the value of the series. The value of $1+2+3+4+5$ is $15$ . No problem. But you can’t do that with an infinite series. You’d never complete the process — and so you can’t get its result.

You learn about infinite series in school, and what you learn is that some series converge to a limit. That is, if you have the infinite series

$S = \displaystyle \sum_{k=0}^{\infty} a_k$

it converges if, loosely speaking, the sequence of partial sums

$S_n = \displaystyle \sum_{k=0}^{n} a_k$

approaches some value $s$ arbitrarily closely as $n$ gets larger; that value is called the limit and we can write

$\displaystyle \lim_{n\to\infty} \sum_{k=0}^{n} a_k = s$ .

And then there’s a bit of a leap as we regard $s$ as not just the limit of the partial sums, but as the value of the infinite series:

$\displaystyle \sum_{k=0}^{\infty} a_k = s$

But not all series have limits, and if the limit doesn’t exist, then we regard the value of the infinite series as undefined.

That all can be learned in an intuitive way, though it can be made much more formal, and on the surface it makes sense. But there’s a sort of swindle going on here. You’re thinking of the “value” of the series as “what you would get if you added up all the infinite number of numbers”… but you can’t add them all up, so how can you assert what you would get if you did?

Here’s a demonstration of why that way of thinking about it is deceptive: the Riemann series theorem. Consider the series

$\displaystyle 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - ...$

You can show this converges to the limit $\ln 2$ . But you can take the same series and rearrange the terms like this:

$\displaystyle \left (1 - \frac{1}{2} - \frac{1}{4}\right ) + \left (\frac{1}{3} - \frac{1}{6} - \frac{1}{8}\right ) + \left (\frac{1}{5} - \frac{1}{10} - \frac{1}{12}\right )...$

and that converges to $\frac{1}{2}\ln 2$ . You’re adding up “the same” numbers in the second series as in the first, and addition is commutative, so you should get the same answer if you could add up all the numbers in the series (which you can’t)… but the limits are different! In fact, Riemann proved that any conditionally convergent series (one that has a limit, but the sum of the absolute values of the terms does not) can be rearranged to give you any limit, including $\infty$ or $-\infty$ , or no limit at all. It seems the “value” of a conditionally convergent series is a property not just of the numbers being summed, but the order they’re being summed in, and that’s not at all true of the value of a finite sum. Really the limit is a number that can be unambiguously associated with an infinite series, and we can define it as that series’s value, but “value” here means something different than in the case of a finite series where it’s just what you get if you add all the terms together. In fact, what the value means is just what it is: the limit of the sequence of the finite sums.

That being said, what about a divergent series?

Stay tuned.

Ramp primes

23 April 201923 April 2019 by Rich Holmes, posted in Numbers

I have no idea who’s gotten to this before me, nothing turns up in Google…

Define the zeroth ramp number R(0) to be 123456789. Then define the nth ramp number R(n) to be R(n-1) with a 1 prepended and a 9 appended: R(1) = 11234567899, R(2) = 1112345678999, and so on.

Likewise, the antiramp numbers R'(n) are R'(0) = 987654321, R'(1) = 99876543211, R'(2) = 9998765432111, and so on.

Then R(17), R(19), and R'(38) are (if the Python primefac library is to be believed) primes. And they are the only ramp/antiramp primes for a good long time. I checked up through R(1000) and R'(1000)… and just when it seemed there were no more, R'(926) turns out to be prime:

9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999876543211111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Thanoseses

19 April 201919 April 2019 by Rich Holmes, posted in Numbers

I saw this tweet:

and my first thought was, “Let’s see, so if each destroys half of all life…”

Or am I getting my pop culture mixed up? Well. Suppose we did have a line of, say, 63 Thanoses. Thani? Thanoxen? Something. One by one they snap their fingers and each time, half of all life is destroyed. You end up with $1/2^{63}$ of all life surviving. About 1.1E-19. Good luck surviving that.

But wait, that’s wrong. The first Thanos snaps and half of all life is destroyed… including half of all Thanoses. Of the 62 who haven’t snapped yet, now there are only 31 of them. After two snaps there are 15 who haven’t snapped. After three there are 7, after four there are 3, after five there is 1. That one snaps and we’re done. The surviving fraction is $1/2^{6} \approx 1.6\%$ . Your odds still aren’t good but they’re enormously better.

6 is $\log_2(63+1)$ ; the surviving fraction is $1/2^{\log_2(64)} = 1/64$ , or $1/2^{\log_2(n+1)} = 1/(n+1)$ for $n$ initial Thanoses.

Well, but not exactly. Presumably this is a random, probabilistic thing. On average half of all Thanoses die on each snap, but there’s some probability they all survive, and some probability they all die. If they all die on the first snap, $1/2$ of us survive; if they all survive every snap, $1/2^n$ of us die. The former is a lot more likely than the latter, though.

I wrote a little Python script and got this distribution of survival fractions with 64 initial Thanoses: [edited after bug fix]

Fraction	Number of times
1/4 or more	0
1/8	671
1/16	54,214
1/32	343,104
1/64	430,491
1/128	152,643
1/256	18,035
1/512	832
1/1024	10

So, good news, in the worst case there still are several million people alive. Just probably not you.

Limited persistence (part 3)

31 March 2019 by Rich Holmes, posted in Numbers

By the way:

I talked about how, instead of checking in base 10 every number up to, say, 10⁴⁰, you can check only numbers with no 0 or 1 digits, that do not have both a 5 and an even digit, with digits in increasing order, and that’s a vastly smaller number to check.

Similarly for other bases, but think about base 3. The only digits you have are 0, 1, and 2, so the only numbers that do not have 0 or 1 digits are all 2s: 2₃, 22₃, 222₃, 2222₃, …

There are 343,585,013,821,340,887,357,640,753,177,080,848,468,071,681,334 numbers that have 100 digits in base 3. Out of those only one needs to be checked (if you’ve already checked the 99 other numbers consisting of fewer 2s). Which is one heck of a speedup.

In base 4, any number with more than one digit equal to 2 has maximum persistence 2, so there are only two numbers per decade worth checking (23₄, 33₄, 233₄, 333₄, 2333₄, 3333₄, …)

So if we want to check numbers up to 100 digits, there are 100 base 3 numbers and 200 base 4 numbers. For base 5, there are 176,850 numbers. 181,900 in base 6, benefiting from the factors of 6, but 96,560,645 in base 7! Still a lot less than 7¹⁰⁰, but things are slowing down pretty hard.

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Like this:

Like this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Like this: