What is the slowest-growing whole number sequence?

December 11, 2013 3:00 PM

What is the slowest-growing non-repeating, non-trivial* whole number sequence?

* In this case, "non-trivial" means not a simple arithmetic (n, n+1, n+2, n+3...) or geometric (n×1, n×2, n×3...) sequence.

My first inclination was to go with the primes (2, 3, 5, 7, 11...). Though if we allow rounding (like a ceiling function), ceil[primes/2] might work (1, 2, 3, 4, 6...).

What do you think? An OEIS search has not turned up anything. I'm sure someone's looked into this before, but as much as my modest research has stumped me, I'm just as interested in the thought process/derivation of the answer. There is probably a really elegant answer I'm missing!

As far as the practical application: Well... say, hypothetically, that one had a password that was required to change every so often (and not change back), and one wanted to keep things simple by just changing (in a not-easily-guessable way) a whole number appended to the end of one's password (one that won't blow up to, say... 80 digits by step #20 or so). [I will not use this method, nor should you. Probably.]

posted by Eideteker to Science & Nature (24 answers total)

Can you define "non-trivial" formally? I don't think you can. A very slow growing sequence with repeating numbers is the inverse Ackerman function.
posted by esprit de l'escalier at 3:13 PM on December 11, 2013 [3 favorites]

How about the list of composite numbers? It's going to grow a lot slower than the list of primes.

The hundredth prime is 541, which means that there were 441 composite numbers by that point.
posted by Chocolate Pickle at 3:14 PM on December 11, 2013 [2 favorites]

It kind of depends on what you're willing to accept.

Composite numbers grow slower than prime numbers.

Non-cubes grow slower than that.

"Everything except for the prime numbers that are palindromes in both base 10 and base 7" grows almost as slow as whole numbers themselves do.
posted by aubilenon at 3:14 PM on December 11, 2013 [1 favorite]

Oops, that palindrome thing does manage to skip 3 of the first 5 whole numbers so maybe it's not that great an example. It does slow down pretty good after that, though.
posted by aubilenon at 3:17 PM on December 11, 2013

I think you're going to have to define non-trivial a bit more strictly, otherwise you'll just end up with something that looks like an arithmetic series in everything but name and derivation, where every so often you skip some whole numbers.
posted by Aleyn at 3:19 PM on December 11, 2013 [1 favorite]

If you relax the restriction that terms in the sequence can't repeat, some interesting candidates include:

-- inverse Ackermann (as noted above by esprit de l'escalier)
-- Davenport-Schinzel
-- the inverse of Friedman's sequence
posted by un petit cadeau at 3:20 PM on December 11, 2013

I'm going to assume that by "non-trivial" you really mean that a random person will have a poor chance of guessing it. This means that things like non-cubes would be bad because a random person would mistake it for just counting numbers. And that you don't really want the slowest growing, but something "slow enough." And that you want it to be easy to calculate the next term when you need to do so.

So how about: 1,2,4,5,7,8,10 . . .
(to get the next term, add the value you get as remainder when you divide by 3.)
posted by Obscure Reference at 3:29 PM on December 11, 2013

In other words, non-multiples of 3.
posted by Obscure Reference at 3:30 PM on December 11, 2013

The arithmetic sequence 1,2,3,... is a lower bound for strictly increasing natural-number sequences: at each step you add at least 1, and if you ever add more than 1, all following numbers in the sequence are larger than their index.

So, what you want is a non-trivial way of determining at which steps you'll add more than 1. I'll arbitrarily define "non-trivial" as non-terminating (so adding 2 at some step and then always adding 1 thereafter doesn't count) and non-repeating (so adding 4 at every fifth step and 1 otherwise doesn't count).

One method that satisfies those requirements is: pick your favorite irrational number, x, and choose a base, n. At the k-th step of the sequence, add 1 plus the k-th digit of the base-n expansion of x. Since there are irrational numbers whose expansions have arbitrarily high density of zeros, you can get arbitrarily close to the counting sequence this way.
posted by zeptoweasel at 3:36 PM on December 11, 2013 [2 favorites]

The sequence 1,3,4,5,6,7,... (all positive integers except 2) is neither an arithmetic progression nor a geometric one, so it satisfies the precise conditions you gave.

So let's strengthen the "nontriviality" condition to say that no tail of the sequence should be an arithmetic progression. Then you'll have to omit infinitely many numbers, at least. But you can omit them at arbitrarily low densities: take all the positive integers except the squares; or if that's too fast-growing, all the positive integers except the cubes; or if that's too fast-growing, all but the factorials; or all but the numbers of the form nⁿ; or all but the Ackermann numbers. If these kinds of sequences are allowed, the problem is then that there's no "least density" subset of the positive integers that you could skip; you can always just skip every other one of what you were skipping before, or every nth, or...

So maybe our nontriviality condition is still not strong enough to get something interesting. Maybe we should try, no *subsequence* of our sequence should be an (infinite) arithmetic progression?
posted by stebulus at 3:48 PM on December 11, 2013

In general, to get a real handle on the answers you're going to have to define your terms and conditions a lot more carefully, particularly the one you're worried about, 'non trivial'.

But also in general and as pointed out above by others, we know the lower bound for increasing whole number sequences, and this is the natural number sequence 1, 2, 3, 4, 5, 6, ...

So we can say pretty definitely that there is no single, slowest growing sequence larger than this. Because given any sequence that is larger than the natural number sequence, you're going to be able to take that sequence and tweak it somewhere to make it just a little bit slower growing yet still larger than the natural numbers.

Then you'll be able to tweak this new sequence a bit to make it even slower growing, and so on.

So we could come up with a whole bunch of sequences of sequences, each larger than the natural numbers but getting smaller and smaller above that limit.

So that is one answer to your question--there is no single smallest such sequence.

I've handwaved at the part where you can take any sequence and make it smaller but still larger than the natural numbers. We could leave it as an exercise to the reader, which is the traditional way in math books, but here is a hint: You can always find somewhere in the sequence where you can subtract 1 from each number in the sequence thereafter--leaving you with a sequence smaller than the one you started with but still larger than the natural numbers.
posted by flug at 4:31 PM on December 11, 2013 [1 favorite]

A more practical answer to your question would be: Use something like a pseudo-random number generator (or even better, a real random number generator) to scramble up all the numbers from say 1 to 10000. Then keep that list somewhere and pick the next number off the list whenever you need it.

This won't give you a monotonically increasing sequence of numbers, but it will give you what you really want, which is a *predictable* sequence of numbers (to you), and all the numbers on the list will be relatively small, and the list and sequence will nevertheless appear pretty unpredictable to the average snooper.

The advantage of the 'pseudorandom number generator' method is you could use something like maybe the mersenne twister formula which you could somewhat easily memorize and then you can generate your list of random numbers whenever you want, without needed to keep a list.

The Mersenne Twister, just for example, gives numbers between 0 and 2^32, which is far larger than you want. But just take the Mersenne Twister results, with certain starting parameters that you would decide upon and memorize, and then take the final result mod 1000 or mod 10000 or whatever and you'll have what you need.

Even simpler would be to use something like an 8th degree polynomial. You choose the coefficients and memorize them. Then put in x=1, x=2, x=3, etc to get your different numbers. Whenever you need a new 'random' number, increase x by one and calculate away. For example:

10 x^8 - 42 x^7 +12 x^6 - 14 x^5 - 3 x^4 + 4 x^3 - 3 x^2 +4 x + 9

If you pick your coefficients carefully (which I haven't, above) could keep the resulting number pretty small for x smaller than 200 or whatever.

Note that none of these methods is really recommended as truly secure or unbreakable. They might be a good sight better than using your birthday and spouse's name as passwords, though.
posted by flug at 4:47 PM on December 11, 2013

What is the slowest-growing non-repeating, non-trivial* whole number sequence?

There is none, of course, unless you play weird, silly games with what you mean by "non-trivial".

You can make an arbitrarily fast-growing sequence. You can take its complement. Voila, you've got an arbitrarily slow-growing sequence. And you can easily and obviously make one slower than that. And slower than that. And slower than that.

I'm not really sure what else there is to say about this. The answer is clearly "there is none".
posted by Flunkie at 4:48 PM on December 11, 2013 [7 favorites]

say, hypothetically, that one had a password that was required to change every so often (and not change back), and one wanted to keep things simple by just changing (in a not-easily-guessable way) a whole number appended to the end of one's password (one that won't blow up to, say... 80 digits by step #20 or so). [I will not use this method, nor should you. Probably.]

Then, hypothetically, one ought not fartarse about with number sequences but instead use password management software and let it regenerate a totally new random password every time a change was required. One should also use the fact that password management software lets one define a lifetime for any password and prompt one when such a password expires. [I do use this method, so should you. Probably.]
posted by flabdablet at 3:27 AM on December 12, 2013

Response by poster: "If you relax the restriction that terms in the sequence can't repeat"

Nope, the password policy won't accept the same password twice.

"Then, hypothetically, one ought not fartarse about with number sequences"

I'm sorry if my playing with number sequences somehow offends you. The password requirement was the prompt for what I thought was an interesting number question, but this is in no way meant to be a literal "help me construct a password" question.

"So maybe our nontriviality condition is still not strong enough to get something interesting. Maybe we should try, no *subsequence* of our sequence should be an (infinite) arithmetic progression?"

See, this is actually helpful. Let's say I'm worried about a nosy nancy looking over my shoulder while I enter my password, and I want to move to the next number in the sequence, but I don't want them to be able to guess what it is. (n, n+1, n+2, n+3...) or (n×1, n×2, n×3...) are pretty easy to guess, so maybe what I want is a sequence where no three terms fit a simple sequence (line or curve?) that a non-compiler could derive just by looking at it. The sequence of composites is interesting, but I worry that it gets too close to (n, n+1, n+2...) fairly early on.

I hope that helps to clarify.
posted by Eideteker at 6:19 AM on December 12, 2013

Response by poster: The sequence, however, should be something that I (someone with the "key") can derive the next number in the sequence without having to perform any complex computations or lookups (i.e., in my head without necessarily memorizing pi to n places and without needing a computer).
posted by Eideteker at 6:30 AM on December 12, 2013

Mod note: Folks, the question is not actually about generating a password; that was just an example. Please drop further password advice. Thanks.
posted by taz (staff) at 6:48 AM on December 12, 2013

Best answer: As a side note (and this doesn't help with your constrains of doing this in your head), a Maximal Linear Feedback Shift Register works well for not growing since it will never grow beyond a certain number of bits. To do it in your head, you need to be able to do decimal->binary, logical-and and logical-xor in your head:

unsigned lsb = lfsr & 1; /* Get lsb (i.e., the output bit). */
lfsr >>= 1; /* Shift register */
if (lsb == 1) /* Only apply toggle mask if output bit is 1. */
lfsr ^= 0xB400u; /* Apply toggle mask, value has 1 at bits corresponding

Which, as I said, doesn't help you much, but there are other approaches to sequence in encoding.

For example, let's say that you break your number into 3 groups of digits: [high][med][low], where low is a single digit, med is 2 digits and high is 3 digits.

You add some l to low and when it overflows you mod by 10 then as overflow you add some m to med and when that overflows you mod by 100 add some h to high. So let's pick l, m, and h to be 5, 12, and 1. Your number sequence is 0, 5, 120, 125, 240, 245, 360, 365, 480, 485, 600, 605...1080, 1085, 1200, etc.

I picked l, m, and h badly as well as the size of each group badly, just so I could get through the set easily enough. By using this grouping, the calculation is fairly easy - the successor of any given number is an easy head calculation, but it's not inherently obvious the pattern. You can also pick negative numbers for l, m, or h (or even better, a mix) and use underflow as a signal to work the next.
posted by plinth at 9:02 AM on December 12, 2013

Best answer: Why an increasing sequence? As Flunkie et. al. noted, there is no slowest-growing sequence, even given the constraint that no tail should be an arithmetic or geometric progression.

(An alternate statement of the proof: let {a_k} be any really fast-growing sequence. Begin with the positive integer sequence 1, 2, 3, .... Drop the a_1st integer, then the a_1 + a_2nd integer, etc.: i.e. drop s_n = a_1 + ... + a_n from the positive integer sequence for each n = 1, 2, 3, .... There is always a faster-growing sequence, so there is always a complementary slower-growing sequence. All sequences constructed in this manner have tails that do not follow a strict arithmetic (and definitely not geometric!) progression.)

But going back to the setup that led to this question, an alternate solution would lead to the question: how can we construct a size-limited (so, bounded) infinite sequence that is easily predictable to generate, but does not have an easily recognized/predictable pattern to guess? Which gets back to the topic of automatic pseudorandom password generation (in the example case, generating just the last, say, two letters of the password), and there's a lot of options and research in that area.

In terms of something you can easily remember or calculate... well, that throws out the idea from above of taking your favorite (non-pi or otherwise special) irrational number, expressing it in your favorite base, then just using subsequent digits (or blocks of digits of fixed length). Pity, I liked that option:-P I think there are relatively simple pseudo-random number generators; you could come up with some fixed calculation that starts with a pseudo-random seed (eg. the date, if you don't change the password exactly daily, but frequently enough that you would remember the date of last password change), then performs some fixed, finite sequence of calculations to generate a number to tack on to the end of your password. (Note: this exact procedure would, in the long run, generate an obvious annually-cyclical pattern, so I give it more in the spirit of demonstrating a general idea.)

But going back to your original question, another criterion that you might want to add to your list of requirements for your sequence is not just that the tail not be an arithmetic sequence, but that finite subsequences not be easily-guessable progressions infinitely often. That is: if you start with the positive integers are drop some but with decreasing frequency, then most of the time someone trying to guess your password by picking the next integer will be correct. Which brings us back around to issues of randomness (in any of its various definitions or guises). There's probably some uncertainty principle that could be (or likely already has been) proved to the effect that one can't simultaneously satisfy extremes for all three requirements of low computational complexity (in a complex-to-humans variation of this idea perhaps) to generate, boundedness or slow growth (i.e. density within the integers), and high computational complexity to guess.

One possible option with at least some probability of producing reasonable-sized numbers might be to take the orbit of some discrete but chaotic system. Something slightly more complicated (and less well-known) than but along the same lines as the 3n+1 problem: start with a positive integer n_0. If it is even, set n_1 = n_0 / 2. If odd, set n_1 = 3*n_0 + 1. Repeat ad infinitum. (Except that in many cases the orbit will reach 1 in finite time, but then for other choices on n_0, we don't know whether or not the orbit will ever reach 1, where by "we" I mean "me, last I paid attention to this particular problem eight or ten years ago", so this may no longer be accurate. But it is, again, merely one illustrative example of a discrete, simple, but chaotic dynamical system.)
posted by eviemath at 9:06 AM on December 12, 2013

On preview, plinth's algorithm, with appropriately chosen parameters, is another good example the sort of discrete chaotic dynamical system I'm talking about.
posted by eviemath at 9:08 AM on December 12, 2013

Best answer: Perhaps a decimal flavour of a Gray Code would suit? Growth happens at the same speed as for normal sequential counting because you're still using the same digits at the same rate, but you only ever change one digit at a time to move from one value to the next. So instead of a normal incrementing count where re-using a digit in any given column also triggers a carry into the column to the left, with a Gray code you do the carry instead of the increment, which you then do on the next count.

So after 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 the next in sequence is 19, then 10, then keep on with 11, 12, 13, 14, 15, 16, 17, 18 at which point you're forced to go to 28 (because you've already used 19), then, 29, 20, 21, 22, 23, 24, 25, 26, 27, 37, 38, 39...

To mix things up a bit you can use any arbitrary ordering of digits that pleases you. For example if I want to base a decimal Gray code on the digit sequence 0852146397 rather than on 0123456789, the sequence would go

0, 8, 5, 2, 1, 4, 6, 3, 9, 7,
87, 80, 88, 85, 82, 81, 84, 86, 83, 89,
59, 57, 50, 58, 55, 52, 51, 54, 56, 53,
23, 29, 27, 20, 28, 25, 22, 21, 24, 26,
16, 13, 19, 17, 10, 18, 15, 12, 11, 14,
44, 46, 43, 49, 47, 40, 48, 45, 42, 41,
61, 64, 66, 63, 69, 67, 60, 68, 65, 62,
32, 31, 34, 36, 33, 39, 37, 30, 38, 35,
95, 92, 91, 94, 96, 93, 99, 97, 90, 98,
78, 75, 72, 71, 74, 76, 73, 79, 77, 70,
870, 878, 875 ...
posted by flabdablet at 9:28 AM on December 12, 2013 [1 favorite]

Maybe this breaks one of your implicit rules, but f(n) = floor(n * (1 + ε)), where ε is as small as you like, seems to fit, since you allowed rounding. Or is that too trivial?
posted by dfan at 9:39 AM on December 12, 2013

Here's a method that grows pretty slowly and can be calculated in your head (or maybe with scratch paper):

Start with a₁=2. For each k, let a_k equal a_k-1 plus the number of prime factors of a_k-1. For a similar sequence that is slightly harder to calculate, and grows slightly faster, but looks "less trivial" for the first several entries, add the number of distinct divisors of a_k-1 instead.
posted by zeptoweasel at 10:18 PM on December 12, 2013 [1 favorite]

A really easy one is based on the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is really easy to calculate and has the benefit that all you need to know is the current and previous numbers to calculate the next number.

The actual Fibonacci sequence is probably too commonly known if you're trying to make something difficult for a casual observer to guess, but you can make your own Fibonacci-style sequence by starting with any two numbers:

1, 4, 5, 9, 14, 23, 37, 60, 97, etc

2, 5, 7, 13, 20, 33, 53, 86, etc.

One thing you could do to keep these (or any other similar method such as those mentioned above) easy to calculate would be to take the answer mod 100. So you add the two numbers together but if the answer is greater than 100 you just knock off the initial '1'. So 99+3=2, 91+20=11, etc.

1, 4, 5, 9, 14, 23, 37, 60, 97, 57, 44, 1, 45, 46, 91, 37, 28, etc

2, 5, 7, 13, 20, 33, 53, 86, 39, 25, 64, 89, 53, 42, 95, 37, 32, 69, etc

These sequences will repeat numbers occasionally (you could just skip those) and eventually repeat the entire sequence but if you're using the password checker that only saves your last 10 passwords you're probably fine and even without that you could get a lot of mileage out of it before needing to change to a different scheme.
posted by flug at 7:50 AM on December 15, 2013