Wikipedia:Reference desk/Archives/Mathematics/2024 August 18

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.

August 18

Recursive matrix

Hi. Has anyone ever considered a matrix of matrices which contains itself as one of the entries? Is there a way to make such a thing make sense?

Duomillia (talk) 00:06, 18 August 2024 (UTC)

Sylvester's construction of Hadamard matrices is recursive. But a matrix which contains itself would normally be called self-referential rather than recursive. Self-referential objects, for example the set A = {A}, are generally considered undefined. In fact there are axioms in place, such as the Axiom of regularity, to rule out such objects, --RDBury (talk) 00:36, 18 August 2024 (UTC)

If the matrix is not homogeneous, it could be some kind of Droste matrix. There are certainly nontrivial rooted trees that have themselves as a subtree – think of the indefinite unfolding of a recursive datatype. It is not clear, though, how such loopy matrices might be useful.  --Lambiam 01:02, 18 August 2024 (UTC)

Is there always a prime obtained as the concatenation of a power of 3*n followed by a 1, if n is a positive integer not == 4 mod 11?

Is there always a prime obtained as the concatenation of a power of 3*n followed by a 1, if n is a positive integer not == 4 mod 11? (If n == 4 mod 11, then all numbers obtained as the concatenation of a power of 3*n followed by a 1 are divisible by 11, thus cannot be prime)

This is the smallest prime obtained as the concatenation of a power of 3*n followed by a 1, for positive integers n<=50, not == 4 mod 11 (could you extend this list to n=100 or n=200?)

1,31
2,61
3,811
5,151
6,181
7,211
8,241
9,271
10,9001
11,331
12,466561
13,23134411
14,421
16,23041
17,1326511
18,541
19,571
20,601
21,631
22,661
23,691
24,194084099617653428060161
25,751
27,811
28,41821194241
29,6585031
30,81001
31,86491
32,751447478108161
33,991
34,1021
35,1051
36,12597121
38,14815441
39,1171
40,1201
41,1231
42,158761
43,1291
44,1321
45,109149939351045840229035237837713687871268015108347375034700496875243120429748722166607421968365088105201721191406251
46,1381
47,198811
49,1471
50,384433593750000000001 220.132.216.52 (talk) 10:24, 18 August 2024 (UTC)

I am not aware of any provable answer to this question. But there's a line of heuristic reasoning that seems to work pretty well for these sorts of questions.

A slightly incorrect, but nevertheless useful, way of thinking about the prime number theorem is that, if you don't know anything in particular about a natural number n, then the "probability" that n is prime is about ${\frac {1}{\log n}}$. I put "probability" in scare quotes because there's no randomness involved; n is either prime or it isn't, and you can figure out which. Still this way of thinking about it seems to have considerable power.

So your question is, for each n, is there a natural number $k>0$ such that $10\cdot 3^{nk}+1$ is prime.

For each such k, the "probability" that this value is prime is about ${\frac {1}{(\log 10+nk\log 3)}}$.

If these outcomes were mutually exclusive for different values of k, we could get the probability that there is some such k by adding them up. Of course they're not mutually exclusive (or I don't see why they should be) but what we're mainly interested in is whether the sum is finite or infinite.

And as it turns out, $\sum _{k>0}{\frac {1}{(\log 10+nk\log 3)}}=\infty$.

So basically we can conclude that, using this slightly unjustified notion of "probability", there is such a k almost surely.

Given that there are only countably many n, and probability is countably additive, and given that you haven't found any counterexample, it seems reasonable to conjecture that for each n there is very likely such a k. --Trovatore (talk) 20:57, 18 August 2024 (UTC)

One problem with this argument is that you're not using the assumption that n is not congruent to 4 mod 11, and in fact there are no primes for such n. Given this, I think it would be prudent to add some additional qualifiers like "barring additional number theoretical coincidences". RDBury (talk) 04:03, 19 August 2024 (UTC)

PS. I'm pretty sure the formula should be $10\cdot (3n)^{k}+1$. I haven't checked but I think your argument still works. --RDBury (talk) 04:14, 19 August 2024 (UTC)

And thus $nk\log 3$ should also be $k\log 3n$. 1.168.139.55 (talk) 05:28, 19 August 2024 (UTC)

Ah, my bad; I misread the question. I thought it was a power of 3ⁿ, then adjoin a final 1 in the decimal representation. --Trovatore (talk) 16:33, 19 August 2024 (UTC)

It occurs to me that I can better motivate the technique of investigating whether the sum is finite or infinite, in the following manner: Let's think of the occurrences for different k not as mutually exclusive, but rather as independent, which makes more sense anyway. Then the probability that there is no such k would be the infinite product $\Pi _{k>0}\left(1-p_{k}\right)$, where we write $p_{k}$ for the "probability" for a particular k, namely approximately ${\frac {1}{\log 10+nk\log 3}}$. This infinite product is zero just in case the sum of the $p_{k}$ is infinite. This fact, or close enough, is presumably treated at our infinite product article. --Trovatore (talk) 22:44, 18 August 2024 (UTC)

See OEIS:A088783. In addition to Trovatore's aforementioned heuristics, primes of the form of a power of $n\geq 2$ followed by a concatenated $1$ (i.e. $10n^{k}+1$) have been found for most small values of $n$, with the exceptions of $n$ congruent to $1\!\!\!{\pmod {11}}$ (which you have already disallowed) or $-1\!\!\!{\pmod {33}}$, both of which have covering congruences, as well as a few sporadic unconfirmed values. The sequence of sporadic values starts $185,338,417,432,537,614,668,743,744,773,\ldots$, with the values divisible by $3$ being $417,432,744,786,\ldots$; in other words, we could almost extend the sequence up to $300$ with the exceptions of $139,144,248,262$, where we don't know if there is such a prime. GalacticShoe (talk) 04:25, 19 August 2024 (UTC)

Well, 537 is also divisible by 3, besides, could you give the list up to n=100? 1.168.139.55 (talk) 05:34, 19 August 2024 (UTC)

My mistake, I was finding divisibility by hand and must've miscounted. In any case, I unfortunately don't have the computing power for it. Based on your list, it would seem you would have a better go of it. GalacticShoe (talk) 05:37, 19 August 2024 (UTC)