Wikipedia:Reference desk/Archives/Mathematics/2023 June 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 25

Does such composite exist?

Is there a composite number c which is both a strong pseudoprime base b (where b is the smallest integer > 1 such that the Jacobi symbol $\left({\frac {b}{c}}\right)$ is -1) and a strong Lucas pseudoprime with parameters (P, Q) defined by Selfridge's Method A? If such composite does not exist, then we have an easier primality test. 42.76.19.193 (talk) 06:05, 25 June 2023 (UTC)

Practical strategy to win at these games

What is the winning position of these games?

1. Give a natural number n, the two people can divide the number by a prime power (sequence A246655 in the OEIS) which divides the number (the number 1 is not considered as a prime power), the person who gets 1 wins.
2. Give a natural number n, the two people can divide the number by a prime power (sequence A246655 in the OEIS) which divides the number (the number 1 is not considered as a prime power), the person who gets 1 loses.
3. Give a natural number n, the two people can divide the number by a power of squarefree numbers (sequence A072774 in the OEIS) (except 1) which divides the number, the person who gets 1 wins.
4. Give a natural number n, the two people can divide the number by a power of squarefree numbers (sequence A072774 in the OEIS) (except 1) which divides the number, the person who gets 1 loses.
5. Give a natural number n, the two people can divide the number by any positive integer (except 1) which divides the number, the first person cannot divide it by n itself to get 1, and the divisor chosen by a person must not be greater than the square of the divisor chosen by the previous person, the person who gets 1 wins, or the person who cannot divide the number (e.g. the divisor chosen by the previous person is 2, but the remain number is 5) loses.
6. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have two numbers r and s with r/s prime number loses.
7. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have two numbers r and s with r/s squarefree number loses.
8. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression wins.
9. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression with prime common ratio wins.
10. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression with common ratio whose numerator and denominator both squarefree wins.
11. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression loses.
12. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression with prime common ratio loses.
13. Give a natural number n, the two people can choose the positive divisors of n (one number can only be chosen at most one time), the person who have three numbers r, s, t which are geometric progression with common ratio whose numerator and denominator both squarefree loses.
14. Give a natural number n, the two people can choose the positive divisors of n, but cannot choose the multiples of any number which is already chosen, the person who chooses 1 loses.

42.76.129.143 (talk) 09:01, 25 June 2023 (UTC)

I just looked at the first few and they were simple variations on the game of nim, have a look at that. This looks like a set of exercises, we're not here to do homework, or at least we'd want evidence you'd actually done some work yourself. There's no evidence you've got stuck with something NadVolum (talk) 09:27, 25 June 2023 (UTC)

What happens if no move is possible? In game 3, n = 2 is not divisible by a power of a square other than 1.  --Lambiam 16:14, 25 June 2023 (UTC)

If you follow the link to OEIS you'l find it points to powers of squarefree numbers,, I think more likely the copied the question down wrong than that they got the wrong link. NadVolum (talk) 16:42, 25 June 2023 (UTC)

Sorry, typo, I meant powers of squarefree numbers instead of powers of square numbers. 1.165.113.141 (talk) 03:25, 26 June 2023 (UTC)

Consider the following game play in game 1:

^A     B
_6⟶2⟶1

There are two possible narrations.

1. A starts with a 6 and turns it into a 2. So B gets this 2 and turns it into a 1. Now A gets this 1 and wins.
2. A starts with a 6 and divides it by 3 to get a 2. Now it is B's turn, who divides this 2 by 2 and gets a 1. So B wins.

The wording is ambiguous; is the number a player "gets" the one at the left end or that at the right end of the arrow?  --Lambiam 07:45, 26 June 2023 (UTC)

To expand on NadVolum's comment a bit, the first four games map to nim-like games by the nim position (a, b, c, ...) corresponding to 2^a3^b5^c... . So 1 and 2 correspond to nim in normal and misère play; strategies for these are well known and described in the article. Meanwhile 3 and 4 correspond to the nim following the "multiple-heap rule" given in the article and which is also known as Wythoff's game. A winning strategy for this, at least for the two heap case, is described in that article, so this is known if not exactly well known. (I don't know if the strategy for three or more heaps is known; perhaps Google will turn up something.) Games 5 and 14 are more complicated since they require the players to keep a history of previous moves instead of just the current position. I don't understand the rules for games 6-13; I thought the position was represented by a single number n, so what are r, s & t? Anyway, the first game translates to nim, and though the strategy is well known it's far from trivial. Apparently, though the game has ancient roots, the strategy was only discovered around 1900 by C. L. Bouton. (I couldn't find a reliable source for this, but it seems like this kind of information should be in the article.) So if this is a set of exercises, which seems likely to me, then perhaps look for a similar mapping from these games to games whose strategy is already known. Many board games can be translated to games where the current position is represented by a single integer; you just have to apply the appropriate Gödel-like numbering. (I'm pretty sure this doesn't work with Taboo, though you never know.).

If I didn't make a programming mistake, these are the cold positions for the 3D and 4D variants of Wythoff's game that sum up to at most 20:

3D: (0,0,0) (0,1,2) (1,1,4) (1,3,3) (0,3,5) (2,2,6) (0,4,7) (3,4,4) (1,5,6) (2,3,8) (0,6,10) (2,4,10) (2,7,7) (5,5,7) (3,6,9) (2,5,12) (1,7,12) (4,5,11)

4D: (0,0,0,0) (0,0,1,2) (0,1,1,4) (0,1,3,3) (0,0,3,5) (1,2,2,3) (1,1,1,6) (0,2,2,6) (0,0,4,7) (0,3,4,4) (2,2,2,5) (0,1,5,6) (1,1,2,8) (1,1,5,5) (2,2,4,4) (0,2,3,8) (1,2,4,6) (1,1,3,10) (2,3,3,7) (0,0,6,10) (0,2,4,10) (0,2,7,7) (1,4,4,7) (2,4,5,5) (0,5,5,7) (1,2,5,9) (1,3,6,7) (0,3,6,9) (1,1,7,9) (2,3,4,9) (3,3,3,9) (3,3,6,6) (0,2,5,12) (2,2,7,8) (0,1,7,12) (0,4,5,11) (1,3,4,12) (1,5,7,7) (2,6,6,6) (3,4,5,8) (4,4,4,8)

--Lambiam 18:13, 26 June 2023 (UTC)

Define the notion of subtuple such that (1,3,4) is a subtuple of (1,2,3,4,5). (These tuples are really bags; the order does not matter but the multiplicity does.) Then the following appears to hold: every (n−1)-tuple occurs exactly once as a subtuple of the cold positions for nD Wythoff.  --Lambiam 18:29, 26 June 2023 (UTC)

Just so you know, I independently calculated some cold positions for the 3D case and the values I got match yours where the results overlapped. So it looks like your programming is probably correct. I computed the (1, x, y) positions for x and y up to 60 and plotted the results. Unlike the (0, x, y) case where the cold positions form two approximate lines, the (1, x, y) case is rather chaotic. Other than the points approximating the same two lines, only a lot more roughly, there doesn't seem to be a pattern. That's about what I expected though; if there was a simple pattern then it probably would be included in the Wythoff's game article. --RDBury (talk) 03:39, 27 June 2023 (UTC)

This generalization of 2D Wythoff's game is an obvious one to consider, or the even more general one with any (finite) number of heaps. The player whose turn it is can select any non-empty subset of the heaps, and any number from 1 to the size of the smallest heap in the subset, and then remove that number of tokens from each heap in the subset. Given how obvious the generalization is, many people must have tried to tackle this, but I did not see any publications on this generalization, which strongly suggests it is a difficult problem. That makes it appear unlikely that the posted set of games comes from a set exercise.  --Lambiam 20:19, 27 June 2023 (UTC)

So can you create OEIS sequences for the “cold” numbers (i.e. numbers corresponding to cold positions) for games 1 to 4? (I found the OEIS sequences (sequence A018219 in the OEIS) and (sequence A018220 in the OEIS) and (sequence A051261 in the OEIS)) 210.243.206.248 (talk) 12:33, 28 June 2023 (UTC)