4
$\begingroup$

tl;dr

How can I generate pseudo-random numbers using only pen and paper?

  • Uniform distribution (or as close as possible)
  • It's pen writing on paper; can't cut, fold, throw or anything like that
  • I'm expecting some formula or algorithm, but a geometric solution, graph or set theory would be ok, too
  • It's really just pen and paper. No clocks or anything external

Details

I took a test where all questions were to be marked as right or wrong, and while correct answers would be worth two points, an incorrect answer would subtract one point.

With that system, if you guess all questions randomly, your expected score should be something around 25% (50% for the half that you got right, minus 25% for those you got wrong).

While that will be not enough for passing the test, it can make a difference when you use that technique on the questions you have no idea how to answer, or which you have no time for a proper analysis (as responses in blank do not add or subtract anything from the final score), since test scores are used for classification.

That got me thinking on how to generate proper random responses for such a task, when all you have is a pen and paper.

For my specific case, it was a binary matter, so much simpler. But I wondered what about multiple choices, where the response set has five or six alternatives.

One simpler option for binary was to just set 'right for odd questions, wrong for even questions', which should produce the same result (yes?).

But I still think this is an interesting question, and my math skills are not enough for the problem. I'm pretty sure that I'll have to mod some number as the final step for getting the actual option. I also thought about using some check digit algorithm on a less random seed, perhaps reusing the last result somehow as input for the next iteration (but I may end up on a non-randomic sequence by doing that).

math.stackexchange already has some questions on this, like this and this.

Of these the responses, I liked the most were @Aaron Toponce's, @coffeemath's and @vrugtehagel's. However, they do not fit the criteria I put for the question (well, none of them is a formula, in the conventional sense, at least)

Edit 1

The question tile was changed from Yet another pen and paper random number generator question to Pen and paper pseudo-random number generator because, after thinking for a while, I came to the conclusion that you can't generate random numbers with mathematics alone and no clocks or anything external, as the question's restrictions listed.

Given a seed and a formula or algorithm, the end results will always be the same, as mathematics is deterministic by nature.

Some of the solutions I pointed above add the nondeterministic element by selecting a point in a drawing, which is fine, but not what I was looking for.

So, the definition of a pseudo-random number generator in the context of this question becomes:

A formula or algorithm, that, given an initial seed, generates a non-cyclic sequence of digits.

The distribution of the digits in the sequence should be balanced.

Edit 2

I have uploaded to gist the Notebook I used to play with the proposed solutions:

https://gist.github.com/caxcaxcoatl/3d469a9728737e51530add73327f9c9f

All mistakes (code or conceptual) there are my own. The solution authors are mentioned on the respective response sections, but I diverged a bit from each of them on the actual code.

Note: I know this is not StackOverflow, but I think sharing this would be interesting for other like-minded people.

$\endgroup$
2
  • $\begingroup$ Can a deck of cards be used? If so you could use the solitaire cypher as a key stream source. $\endgroup$ Commented Sep 14, 2019 at 4:44
  • $\begingroup$ @Q the Platypus, no just pen and paper... nothing external $\endgroup$ Commented Sep 14, 2019 at 5:07

3 Answers 3

1
$\begingroup$

I would use a linear congruential generator. Given a seed $X_n$ it returns $X_{n+1}=aX_n+c \pmod m$ for parameters $a,c,m$. I would then take some low order bits of $X_{n+1}$ as the random number. The calculation is not much even with pen and paper. You could use a relatively small $m$ because you don't need many bits. You would like $m$ to be prime, but if it has some large factors that is probably not so bad for this use. $a$ should be near $\sqrt m$ and coprime to it. You can seed it with $X_0$ being your birthday or some such.

$\endgroup$
3
  • $\begingroup$ That's exactly what I was looking for. After reading the Wikipedia article, I experimented a bit and ended up with m=97, a=13 and c=0 (though I have no idea what a primitive element is, or if 13 can be considered as such in this context). This produces a cycle of length 96, almost perfectly balanced for mod 2, 5 and 10. For mod 2, the cumulative sum of the frequencies of 0 and 1 got a somewhat big difference between items ~30 and ~90 (for a seed of 7), but I think this would be too convoluted a process for mod 2, anyway. $\endgroup$ Commented Sep 15, 2019 at 3:35
  • $\begingroup$ just one thing, I think the way you wrote the formula in your response is incorrect. The way it is, I read the modulus operation happening on c alone, and not on aXn + c $\endgroup$ Commented Sep 15, 2019 at 3:40
  • 1
    $\begingroup$ A primitive element $a \bmod m$ is one that the smallest $k$ such that $a^k\equiv 1 \pmod m$ is $k=m-1$ If $m$ is prime there will be a number of primitive elements. They generate the multiplicative group $\bmod m$, so all numbers from $1$ to $m-1$ can be represented as powers of $a$. An example that is primitive is $3 \bmod 7$ because the powers of $3$ are $3,2,6,4,5,1$, while $2 \bmod 7$ is not primitive because the powers of $2$ are $2,4,1$ and do not include $3,5,6$ $\endgroup$ Commented Sep 15, 2019 at 4:41
1
$\begingroup$

Square roots

One solution would be to use the digits of the square root of a number, such that the square root is not an integer (perfect square).

In that case, the square root should be an irrational number, which is acyclic by definition.

Analyzing this option for the numbers below 100 (with digits for the integer part of the square root plus 100 digits after the dot), I found that the balance between the generated digits is not always fair.

For the actual generated series, the average of the standard deviation was 3.034, with a maximum of 15.044 and a maximum difference between min occurrences and max occurrences of 15 (avg 9.433).

That is, counting the occurrence of each digit on a square root (limited to 100 after the dot) and calculating the standard deviation, then doing that for all non-perfect squares below 100 and taking the average of these results, the result is 3.034.

For the series mod 5 (that is, each element mod 5, for the situations where there are 5 options to choose from), the average standard deviation was 4.139 with a maximum of 7.778 and max diff of 21 (avg 10.178).

For the series mod 2 (true/false), average standard deviation of 5.971, max of 21.213, max diff of 30 (specifically for mod 2 of the digits in the square root of 41, 0 appears 65 times, 1 appears only 35 times), average of 8.444.

I'm not accepting this as the answer for my own question because:

  • The analysis above shows the distribution can be quite unbalanced
  • Calculating the square root by hand is somewhat expensive; a simpler algorithm would be welcome
  • I'm just generally looking for other options
$\endgroup$
1
$\begingroup$

Here is a solution that just uses the exam paper itself to do the pen and paper calculations. First I’m going to give a simplified version for true/false questions then explain how you can convert it into multiple choice.

The first 8 true or false questions are your seed so you have to pick them for yourself. Now counting backwards from the last question answered look at the 4th , 5th, 6th and 8th answers if there is an odd number of trues then write true otherwise write false. Repeat this sequence until you run out of questions.

This will create a linear feedback shift register with a cycle time of 255 steps. A longer sequence can be made with a seed of 16 and counting back 4, 13, 15,16.

You can convert this for multiple choice by treating the choice as a pair of true false questions. A = TT b=TF c=FT d=FF

$\endgroup$
3
  • $\begingroup$ Very interesting. Algorithmic and looks very simple. I just need some clarification: when you refer to the last answered question, are you actually referring to the last item of the seed? Looking at the Wikipedia article, it looks like it does not require any input other than the initial seed. Or is the actual last answered question input into it somehow? $\endgroup$ Commented Sep 15, 2019 at 23:27
  • $\begingroup$ The last answered question. So it will be the eighth question at first, then as you fill in the ninth question it becomes the last question at the place you start counting from. $\endgroup$ Commented Sep 15, 2019 at 23:36
  • $\begingroup$ @Q, Ok, I think I got it. So, I fill the first eight with some values out of my head, and then the rest of the test with the register. As I would have already answered some random questions in the test, I found it easier to use the register disconnected from the order of the questions: I start with a seed, say, TFFTFTTF, then I apply the algorithm whenever I want to fill a question with a random value (say, question 37, if I know I won't be able to answer it, then 29, if that's the next one I need) $\endgroup$ Commented Sep 16, 2019 at 3:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .