Magic 7 finite state machine

Consider the riddle in the following video

You can solve it as follows: You can write any number as $$x = \overline{x_nx_{n-1}...x_1x_0}$$ With the overline meaning concatenation, and $x_i$, the different digits of $x$. This notation is a shorthand for $$x = \sum 10^i x_i$$ We can rewrite this sum using distributivity to be $$ x = x_0 + 10(x_1 + 10(x_2 + ... )))$$ If we define our instuction $f_{x_i}$ as $$f_{x_i}(a) = x_i + 10a$$ Then $x$ can be written as $$ x = f_{x_0}(f_{x_1}(f_{x_2}( ... ))) $$ or $$ x = f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}(x_n) $$ But as $f_{x_n}(0) = x_n$, it is more natural to write it as $$ x = f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}\odot f_{x_n}(0) $$ We are only interested in whether or final result is a multiple of 7, ans as we only use multiplication and addition, we can consider the the full system in mod 7. $$ x \equiv f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}\circ f_{x_n}(0) (\mod 7)$$ This formula now represents a finite state machine with 7 states, (0,1,2,3,4,5 and 6) and 10 instructions ($f_0$ to $f_9$), where the final state is the same a s the remainder of the original number when dividing by 7.

	0	1	2	3	4	5	6
0	0	3	6	2	5	1	4
1	1	4	0	3	6	2	5
2	2	5	1	4	0	3	6
3	3	6	2	5	1	4	0
4	4	0	3	6	2	5	1
5	5	1	4	0	3	6	2
6	6	2	5	1	4	0	3
7	0	3	6	2	5	1	4
8	1	4	0	3	6	2	5
9	2	5	1	4	0	3	6

Now, if we call state 0 X, state 1 A, state 2 C, state 3 F, state 4 B, state 5 D and state 6 E, we arrive at the transition table given by the riddle. So by consequence, the transition table works as a division test by 7.

Salamander riddle

Riddle

On a particular island live a lot of salamanders with different colours. Each salamander is defined by its genetics, an ordered list of unordered pairs of so-called genes. These genetics have the following properties:

1. A child of two salamanders will, for each gene pair, select one random gene from each parent and form a new gene pair with the two selections. (Kind of like how it works in real biology if we ignore random mutations and crossing over).
2. Two salamanders with the same gene pairs (so they are exact clones of each other) will have the same colour.
3. Two full siblings (so salamanders with the same parents) have the same colour (totally not how it works in biology).

Note that not all gene combinations have to be viable, so not every gene combination has a corresponding salamander.

Prove that two salamanders with different colours cannot have viable offspring.

Solution

Assume a salamander $X$ has genes $(x_1, x'_1), (x_2, x'_2), ...$ and a salamander $Y$ has genes $(y_1, y'_1), (y_2, y'_2), ...$. And they have viable offspring $Z$ with genes $(x_1, y_1), (x_2, y_2), ...$.
$X$ and $Z$ can have offspring genetically identical to $Z$ (by selecting $x_i$ from $X$ and $y_i$ from $Z$). And can have offspring that is genetically identical to $X$(by selecting $x'_i$ from $X$ and $x_i$ from $Z$). Therefore using the third axiom, $X$ and $Z$ have the same colour. Analogously, $Y$ and $Z$ have the same colour. By consequence, $X$ and $Y$ have to be the same colour.
You can find a more rigorous version of this proof that is a computer verified here: https://gitlab.com/Elmosfire/blog-links/-/blob/378a210994d4e5d5f96af505ebf1011aecbfca3f/salamander.lean.

Alternate version

If we soften the third axiom to be

Two full siblings have the same colour if neither of them is genetically equal to their parents.
In this case, a salamander can breed with another salamander of a different colour and produce viable offspring.
Assume there are three gene pairs, all with two possible genes. Call them r/R, g/G and b/B.
Then have only six viable gene combinations,
rRGGbb, rRggBB which are red.
rrgGBB, RRgGbb which are green,
RRggbB, rrGGbB which are blue.
And let each time call the first mentioned geneset to have left chirality and the right mentioned geneset to have right chirality.

Note that genesets of the same chirality are symmetric to one another by replacing r with g, g with b and b with r. Genes from the left chirality transform into genes with right chirality by swapping two genes.

Now we can check all cases:

• If a salamander breeds with a clone of itself, the only viable offspring is itself. For example, if rRGGbb breeds with itself, the offspring can only be RRGGbb, rRGGbb and rrGGbb, of which only the middle one is viable.
• If a salamander breeds with a salamander with the same chirality, it has one viable offspring. For example rRGGbb and rrgGBB only have rrGGbB as viable offspring.
• Two salamanders with the same colours but different chirality cannot have viable offspring.
• If two salamanders with different colours and chirality have offspring, the offspring always is a clone of one of the parents.
  If this argument does not convince you, you can check the system case by case:

rRGGbb(  red) & rRGGbb(  red) => <rRGGbb(  red)>
rRGGbb(  red) & rrgGBB(green) =>  rrGGbB( blue) 
rRGGbb(  red) & RRggbB( blue) =>  RRgGbb(green) 
rRGGbb(  red) & rRggBB(  red) => 
rRGGbb(  red) & RRgGbb(green) => <rRGGbb(  red)> or <RRgGbb(green)>
rRGGbb(  red) & rrGGbB( blue) => <rrGGbB( blue)> or <rRGGbb(  red)>
rrgGBB(green) & rRGGbb(  red) =>  rrGGbB( blue) 
rrgGBB(green) & rrgGBB(green) => <rrgGBB(green)>
rrgGBB(green) & RRggbB( blue) =>  rRggBB(  red) 
rrgGBB(green) & rRggBB(  red) => <rrgGBB(green)> or <rRggBB(  red)>
rrgGBB(green) & RRgGbb(green) => 
rrgGBB(green) & rrGGbB( blue) => <rrgGBB(green)> or <rrGGbB( blue)>
RRggbB( blue) & rRGGbb(  red) =>  RRgGbb(green) 
RRggbB( blue) & rrgGBB(green) =>  rRggBB(  red) 
RRggbB( blue) & RRggbB( blue) => <RRggbB( blue)>
RRggbB( blue) & rRggBB(  red) => <RRggbB( blue)> or <rRggBB(  red)>
RRggbB( blue) & RRgGbb(green) => <RRggbB( blue)> or <RRgGbb(green)>
RRggbB( blue) & rrGGbB( blue) => 
rRggBB(  red) & rRGGbb(  red) => 
rRggBB(  red) & rrgGBB(green) => <rrgGBB(green)> or <rRggBB(  red)>
rRggBB(  red) & RRggbB( blue) => <RRggbB( blue)> or <rRggBB(  red)>
rRggBB(  red) & rRggBB(  red) => <rRggBB(  red)>
rRggBB(  red) & RRgGbb(green) =>  RRggbB( blue) 
rRggBB(  red) & rrGGbB( blue) =>  rrgGBB(green) 
RRgGbb(green) & rRGGbb(  red) => <rRGGbb(  red)> or <RRgGbb(green)>
RRgGbb(green) & rrgGBB(green) => 
RRgGbb(green) & RRggbB( blue) => <RRggbB( blue)> or <RRgGbb(green)>
RRgGbb(green) & rRggBB(  red) =>  RRggbB( blue) 
RRgGbb(green) & RRgGbb(green) => <RRgGbb(green)>
RRgGbb(green) & rrGGbB( blue) =>  rRGGbb(  red) 
rrGGbB( blue) & rRGGbb(  red) => <rrGGbB( blue)> or <rRGGbb(  red)>
rrGGbB( blue) & rrgGBB(green) => <rrgGBB(green)> or <rrGGbB( blue)>
rrGGbB( blue) & RRggbB( blue) => 
rrGGbB( blue) & rRggBB(  red) =>  rrgGBB(green) 
rrGGbB( blue) & RRgGbb(green) =>  rRGGbb(  red) 
rrGGbB( blue) & rrGGbB( blue) => <rrGGbB( blue)>

If the salamander is in <>-brackets, it means it is a clone of one of the parents. You can quickly check two full siblings where none are a clone of either of the parents do not exist.
So the last hypothesis is fulfilled automatically.

Uncountably infinite elves.

Problem Statement

The original can be found here: https://www.reddit.com/r/mathriddles/comments/mgsg6n/a_game_between_elves/

The empress has organised a game for the elves of elf city. In her very large park she has positioned stations, each labelled by a non-negative real number. Initially, there is an elf at each station. Because there are so many elves, she has had to create many stations — indeed, every \(x \geq 0\) corresponds to some station \(S_x\).

The empress will have elves run between stations in the following way: at every station \(S_x\) where \(x > 0\), there is a note telling the elves currently positioned there where they should go next. Crucially, the index of this next station will always be smaller than the index of the current one (so if at \(S_x\) the note says to go to \(S_y\), we must have \(y < x\)). The station \(S_0\) does not have a note: if an elf reaches \(S_0\), they stay put. Every time the horn is blown, all elves travel to their next station, and wait till the next horn blow. The game ends after \(\omega\) horn blows (elves live forever, of course).

Is it possible for uncountably many stations to be occupied when the game ends?

(as with previous elf problems, AC is a law of the land)

Mathematical formulation

This problem can be reformulated mathematically.

Build a function \(f\) with the following properties.

• \(f: \mathbb{R}^+ \rightarrow \mathbb{R}^+ \)

• \(\forall x > 0 \in \mathbb{R}, f(x) < x\)

• \(f(0) = 0\)

• \(\forall y \in \mathbb{R}, \exists x \in \mathbb{R} : \lim_{n \rightarrow \infty} f^n(x) = y\)

Note that \(\forall n, \forall y \in \mathbb{R}, \exists x \in \mathbb{R} :f^n(x) = y\)

Is not sufficient to make this work in the limit.

Because obviously \(f(x) = x/2\) works for every \(n\), but \(\lim_{n \rightarrow \infty} f^n(x) = 0\)

Solution

Let us note \(\lim_{n \rightarrow \infty} f^n(x)\) as \(f^\omega(x)\).

Consider the equivalence relation \(x \sim y \Leftrightarrow x-y \in \mathbb{Q}\)
Call the partitions created by this equivalence relation \(\mathcal{S}\)

The fact that this relation is an equivalence relation is trivial. The partitions \(\mathcal{S}\) has the following properties:

• Each subset is dense in the positive reals (cause \(\mathbb{Q}\) is)

• Each subset is countable (cause there exists bijection with \(\mathbb{Q}\))

• There are uncountable subsets (cause the union is uncountable, and each set is countable).

According to the Axiom of choice, there exists an bijection from \(\mathcal{S}\) to \(\mathbb{R}\). Call this bijection \(\mu\).

Create for each \(S \in \mathcal{S}\) a subset \(T_S\) defined by \[T_S = \left\{s \in S \middle| s > \mu(S) \right\}\]

This set of subsets \(\mathcal{T}\) has the following properties:

• All subsets are disjunct.

• Each subset is dense in the reals larger than \(\mu(S)\).

• Each subset is countable

• There are uncountable subsets

Define \(\mu'\) such that \(\mu'(T_S) = \mu(S)\).

Now note that \(\inf T_S = \mu'(T_S)\) This is trivial because the subset is dense in the reals larger than \(\mu'(T_S)\).

From this follows that for each \(T_S\) there exists a deceasing sequence that as \(\mu'(T_S)\) as limit. Call this \(a_{TS}\).

Define \(\varphi : T_S \rightarrow \mathbb{R}\) such that \(\varphi(x)\) equals the first value in \(a_{TS}\) smaller than \(x\). This is well defined, as the limit is lower than \(x\) so a value exists.

Define \(\phi : \mathbb{R} \rightarrow \mathbb{R}\) such that \(\phi(x)\) is \(\varphi(x)\) if \(x \in T_S\), and 0 otherwise. As all options for \(T_S\) are disjunct, this is well defined.

After one application, the value becomes an element of the sequence \(a_{TS}\). After another application of the function, the value becomes an element further on in the sequence. This means that the sequence \(\phi^i(x)\) for \(i > 0\) is a subsequence of \(a_{TS}\), so as \(a_{TS}\) converges to \(\mu'(T_S)\), so does \(\phi^i(x)\).

This means that if \(x \in T_S\) then \(\phi^\omega(x) = \mu'(T_S)\)

This means that the range of \(\phi^\omega(x)\) is the range of \(\mu'\), which is the range of \(\mu\) which is all real numbers. So we have found the function we where looking for.

Prime number sided die

Puzzle

Assume you roll 3 p-sided die, with p a prime larger than 3, and instead of looking at the individual value, you look at the sum of all three die, and the sum of the squares, and take these 2 values modulo p.

For example, if you have 7 sided die and you roll 3,4,5, then the sum is 12 and the sum of squares is 50, so the result would be (5,1), as $12\equiv 5 \pmod 7$ and $50 \equiv 1 \pmod 7$

This procedure generates p² possible values. Proof that p² − p of these outcomes are equally likely, and that the remaining p values also are equally likely.

Solution

For the the rest of the solution, if we use ≡, we mean $\equiv \pmod p$

Call the values of the die a, b and c

To get the likelihood of an outcome (x, y) we have to count the number of solutions of
$$\begin{cases}a+b+c &\equiv x \\a^2+b^2+c^2 &\equiv y\end{cases}$$

Now call f(x, y) the number of solutions matching these equations

Define α :  ≡ a − x/3, β :  ≡ b − x/3, γ :  ≡ c − x/3, ω :  ≡ y/2 − x²/6

As p is coprime with 2 and 3 and prime, this is well defined.

Using these definitions, after some simple aritmatic, our equations become the following:

α + β + γ ≡ 0

α² + β² + γ² ≡ 2ω

Note that for every solution that exists for these equations, there exist p in the original one, namely, one solution for every value of x. In other words, the number of solutions f(x, y), is the number of solutions for the above equation, if we state that ω :  ≡ y/2 − x²/6. Let us call this f(ω)

In our equations, γ ≡  − α − β so

α² + β² + ( − α − β)² ≡ 2ω

2α² + 2β² + 2αβ ≡ 2ω

α² + β² + αβ ≡ ω

This is a quadratic equation in α, and thus, The number of solutions for a given β is determined by the determinant:

D ≡  − 3β² + ω

Call Θ(d) a function that is the number of solutions that x² ≡ d has. This function can be refined in detail using Eulers Criteria, but in essence, this function is always 0 or 2, except when d = 0, then it is one. This function also has the nice property that Θ(r) = 2 ⇒ Θ(d) = Θ(rd)

The total number of possible solutions for different β can now be stated as

∑_βΘ( − 3β² + ω)

Now assume that ω is nonzero.

Now as p is an odd prime, we can always find an n such that
ω ≡ 4ⁿ

Now define ξ ≡ b/2ⁿ.

As there exists one β for each ξ, so the number of solutions for ξ is equal to the number of solutions for β.

∑_ξΘ((1 − 3ξ²)4ⁿ) = ∑_ξΘ((1 − 3ξ²))

So the counting function is independent on the value of ω as long as it is not zero. This makes up p² − p of original cases.

Now assume ω is zero.

∑_βΘ( − 3β²) = ∑_βΘ( − 3) = pΘ( − 3)

So this counting function is also constant if ω is p, which makes the other p cases.

Dice

Imagine you try to simulate a single six-sided die roll by rolling a large number of die, using the following system: 1. Roll a die 2. Check what number appears the most frequent 3. If there is a single number, take that number 4. If there is a tie, scrap both and continue.

For example, if you roll

132 ⚀’s, 144 ⚁’s, 120 ⚂’s, 97 ⚃’s, 101 ⚄’s and 118 ⚅’s

Then your result is ⚁ cause 144 is the highest.

If you roll 144 ⚀’s, 144 ⚁’s, 120 ⚂’s, 97 ⚃’s, 101 ⚄’s and 118 ⚅’s

Then ⚀ and ⚁ tie, so they are scrapped, so the highest remaining is ⚂.

The question now is the following:

For what number of dice (n) is this method: 1. Well defined 2. Does it produce the numbers 1 to 6 with equal chance

and does this work for dice with other than 6 sides?

First off, the fact that it produces all number with equal chance can be explained by a simple isomorphism argument.

The only thing that is needed to proof this is well defined, is to make sure that not all numbers are tied. There are different ways in which the frequencies can all tie, namely

2-2-2 tie, for example 0x⚀ 0x⚁ 1x⚂ 1x⚃ 3x⚄ 3x⚅ (roll: ⚂⚃⚄⚄⚄⚅⚅⚅ for 8 dice) 2-4 tie, for example 1x⚄ 1x⚅ (roll:⚄⚅ for 2 dice) 3-3 tie for example 1x⚃,1x⚄,1x⚅ (roll: ⚃⚄⚅ for 3 dice)

But for the first two ties, this can only happen if the number of die is a multiple of 2, and for the last die, this can only happen if this is a multiple of 3.

This means that if the number of die is not a multiple of 2 or 3, the frequencies cannot tie.

The argument in the other direction is similar. If n is a multiple of 2, then n/2 fives and n/2 sixes will tie. Same if n is a multiple of 3, then n/3 fours, fives and sixes will tie.

For all other n

n = 2,3 or 4 has a similar argument.

And for 5, and all numbers starting from 7, there is a tie of the form

2-3-x with x a positive integer that is not one (if it was one, that one die would not be tied).

And if we assign a frequency of zero to the x, this turns into the question, can be find for each positive number n two positive integers p and q such that 2p + 3q = n. Ans this is obviously true if n is not one.

What set is larger

Which set is larger for a given number c

• All unordered distinct pairs of natural numbers (a, b) such that c = lcm(a, b)

• All unordered distinct pairs of natural number (a, b) such that 1/a + 1/b = 1/c

I claim that both these sets are equal to the number of unordered distinct pairs (x, y) such that xy = c²

Do proof this, we just have to find two bijections that project x,y on a,b such that both expression are equivalant.

Least common multiple

See this injection
$$\left\{ \begin{matrix}a = \gcd(x,\sqrt{xy})\\b = \gcd(y,\sqrt{xy})\end{matrix}\right. \Leftrightarrow \left\{ \begin{matrix}x=a^2/\gcd(a,b)\\y=b^2/\gcd(a,b)\end{matrix}\right. $$

We know have to proof 2 things. First that this is actually consistent, and secondly that it projects the right sets onto each other.

Consistency

Let us plug in the equations on the right, into the equations on the left
$$\begin{aligned} a' &= \gcd(x,\sqrt{xy})\\ &= \gcd(a^2/\gcd(a,b),\sqrt{a^2/\gcd(a,b)b^2/\gcd(a,b)})\\ &= \gcd(a^2/\gcd(a,b),ab/\gcd(a,b))\\ &= \frac{a}{\gcd(a,b)} \gcd(a,b)\\ &= a \end{aligned} $$

Analog for b.

Closed (left)

If
xy = c²

Then is
$$\begin{aligned} \gcd(x,y) &| x\\ \gcd(x,y) &| y\\ \gcd(x,y)^2 &| xy\\ \gcd(x,y)^2 &| c^2\\ \gcd(x,y) &| c\\ xy/c &|xy/\gcd(x,y) \\ c &|\text{lcm}(x,y) \end{aligned}$$
Thus

$$\begin{aligned} \text{lcm}(a,b) &= \text{lcm}(\gcd(x,\sqrt{xy}),\gcd(y,\sqrt{xy}))\\ &= \gcd(\sqrt{xy},\text{lcm}(x,y))\\ &= c \end{aligned}$$

Closed (right)

If
c = lcm(a, b)

Then

$$\begin{aligned} xy &= a^2/\gcd(a,b) \times b^2/\gcd(a,b)\\ &= \text{lcm}(a,b)^2\\ &= c^2 \end{aligned}$$

Sum of fractions

See this injection
$$\left\{ \begin{matrix}a = x+c\\b = y+c\end{matrix}\right. \Leftrightarrow \left\{ \begin{matrix}x=a-c\\y=b-c\end{matrix}\right. $$

The consistency of this injection is trivial.

That this is closed can be proved as follows:

$$\begin{aligned} \frac{1}{x+c} + \frac{1}{y+c} &= \frac{1}{c}\\ \frac{x+c+y+c}{(x+c)(y+c)} &= \frac{1}{c}\\ \frac{x+y+2c}{xy+xc+yc+c^2} &= \frac{1}{c}\\ xc+yc+2c^2 &= xy+xc+yc+c^2\\ c^2 &= xy\\ \end{aligned}$$

Two fake coins

Puzzle found here.

Among a pile of n gold coins, 2 of them are fake. Fake coins weigh the same, gold coins weight the same, but a fake coin weigh less than a gold coin. Given a balance scale with 2 weighting, the goal is to deduce which are the fake coins. 1. What is the maximum n and be able to achieve the goal? Support your answer with an algorithm. 2. What about with 3 weighting. 3. What about with 4 weighting.

Single fake coin

If there is only a single fake coin, the solution is very simple:

1. Divide pile of coins into 3 equally sized piles (or as close as possible) certainly make sure the first two piles are exactly equal, the third pile may be one more or less.
2. Weight one pile against the second
3. If one of the piles is lighter, continue with lighter pile
4. If the scale is balanced, continue with the third pile.
5. Continue until only one coin is left.

There are solutions to a stricter form of the puzzle, like for example, if you have to write down all your weightings on the beforehand, and I will explain this in a future blog post.

Upper bound

Let us call a specific pair of fake coins a configuration. The different weighting have to be able to distinguish all configurations. A weighting itself can distinguish 3 configurations (if for one configuration left is heavier, for another right is heavier and for the last one the scale is balanced.)

This means that a maximum of w weightings can distinguish 3^w different states.

Contrary to this, the number of possible configurations is ${2 \choose n} = \frac{n(n-1)}{2}$ for n weightings [source].

As all different configurations need to be distinguished, this means:

$3^w \geq \frac{n(n-1)}{2}$

$w \geq \log_3{ \frac{n(n-1)}{2}}$

as as the number of weightings is an integer

$w \geq \left\lceil \log_3{ \frac{n(n-1)}{2}} \right\rceil$

Is a lower bound for the number of weightings needed to distinguish n coins.

Anologous is

$\begin{aligned} 3^w &\geq \frac{n(n-1)}{2}\\ 2\times 3^w &\geq n(n-1)\\ 2\times 3^w &\geq n^2 - n\\ 0 &\geq n^2 - n - 2\times 3^w \\ n &\leq \frac{1 + \sqrt{1+8\times 3^w}}{2}\\ n &\leq \left\lfloor\frac{1 + \sqrt{1+8\times 3^w}}{2}\right\rfloor \end{aligned}$

An upper bound for the number of coins that can be distinguished.

To show that this upper bound can be reached, we just need a strategy that can reach the upper bound.

Sieving

Let call a subset of configurations that is still possible after a set of weighting a sieve. And let us call a sieve solvable in w weightings if there exists a strategy that can find the correct configuration of 2 fake coins in w or less weightings. Let us write out this definitions more mathematical, so we can more easily work with it.

The first thing we do is number each coin, with an index from 0 to n − 1

Definition 1 A configuration is a unordered pair of coins (integers). The set of all configurations C is the set of all unordered distinct pairs of integers in the range [0, n[

Definition 2 A weighting is an ordered pair of disjuct subsets of the integer range, of the same size. (the set of coins we put in the left scale and the set of coins we put on the right scale.)

Definition 3 Each weighting splits a sieve in three smaller sieves, depending on how the scale would react to the configuration. (so the configurations where the left side would be heavier, the configurations where the right side would be heavier, and the configurations would leave the scale balanced )

Theorem 1 If a sieve is solvable in w weightings, there exists a weighting that splits are sieve into 3 sieves that are solvable in w − 1 weightings.

Proof: Trivially proven by induction

Theorem 2 A sieve solvable in w weightings has at most 3^w elements.

Proof: Trivial

Strategy

Using the previous chapter, we can devise an algorithm to search for a strategy. For each sieve, find a weighting that splits it into 3 sieves with at most 3^w − 1 elements, but to make sure that we have margin for future weightings, we will try to split the sieve as evenly as possible. A good metric for how evenly something is split is the product of the sizes of the subsieves, but using this as an heuristic will put (0,0,2) on the same footing as (0,1,1), we will first add one to it, to prevent multiplication with zero.

To device the full strategy, we will use a Monte-Carlo simulation. This is the full algorithm:

1. Select a limit l
2. Start by creating a sieve containing all possible configurations.
3. For each sieve:
   1. Generate l weightings
   2. Select all valid weightings (where all subservient are smaller than 3^w − 1 with w the number of weightings left).
   3. Choose the valid weighting with the best heuristic. (As valid weightings always have better heuristics than invalid ones, these step can be switched with the previous one.)
   4. If there are no valid weightings, goto step 1 and increase the limit.
   5. Add the three new sieves to the set of step 3.
   6. If any of the sieves only has one element, this configuration is the correct configuration, do not add this sieve.

This algorithm does not guarantee a solution will be found, but it will usually find it.

The algorithms are displayed in interactive graphs. Each weighting is displayed as a box, with two sets of numbers in it, separated by <|>. The left set of numbers are the coins that have to be placed on the left set scale, the right numbers are the coins that have to be placed on the right scale. Each box can be clicked to expand or retract it. Expanding the box shows 3 path. The left one needs to be followed if the left scale is lighter, the right one if the right scale is lighter, and the middle one if the scale is balanced. If there are just 2 numbers with an ampersand between them, it means that those are the two fake coins.

Using this algorithm, I found solution for the following settings:

number of weightings	upper limit	number of coins for algorithm	strategy link.
2	4	4	[link]
3	7	7	[link]
4	13	13	[link]
5	22	22	[link]
6	38	38	[link]
7	66	66	[link]
8	115	115	[link]

Further reading:

this paper contains solutions up to w = 10: http://www.chgk.info/~knop/math/ff.pdf