Wikipedia:Reference desk/Archives/Mathematics/2020 August 16

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 16

Fast way to determine if is squarefree

Is there a way to determine whether or not an integer is squarefree that is computationally faster than factoring it up to the point at which you can tell? Bubba73 ^{You talkin' to me?} 04:21, 16 August 2020 (UTC)

The Möbius function $\mu$ has the property that $\mu (n)\neq 0$ if and only if $n$ is square-free. Our article on the function gives a closed formula for computing $\mu (n)$ directly, without having to factorize $n$; see the section Properties and applications. However, this is quasilinear in $n$, which means it is exponential in $\log ~n$, whereas direct factorization of $n$ is sub-exponential. This is a round-about way of saying "I don't know", but if a computationally faster way was known, I think my (limited) investigation would have brought something up.  --Lambiam 06:57, 16 August 2020 (UTC)

Thanks for the interesting information. Bubba73 ^{You talkin' to me?} 16:27, 16 August 2020 (UTC)

@Bubba73: From Square-free_integer#Square-free_factors_of_integers: “No algorithm is known for computing any of these square-free factors which is faster than computing the complete prime factorization. In particular, there is no known polynomial-time algorithm for computing the square-free part of an integer, nor even for determining whether an integer is square-free.” It is accompanied by a citation in the article. —JBL (talk) 10:51, 20 August 2020 (UTC)

Thank you. Bubba73 ^{You talkin' to me?} 15:16, 20 August 2020 (UTC)

Repeating decimals

It can be shown that if a real number has a periodic decimal representation, then it is a rational number. And that all rational numbers have either a finite or a periodic decimal representation. But can one also show that if a real number has a non-periodic decimal representation, then the number is irrational?

Consider $x=0.10110111011110\ldots$ (i.e. one ”1” added each time). This is not periodic.

What troubles me is rational numbers may have several different decimal representations (eg. 0.999… = 1). Could a rational number have a non-periodic decimal representation, in addition to the periodic one[s]?

Thank you. — Preceding unsigned comment added by 94.255.178.165 (talk) 14:47, 16 August 2020 (UTC)

The proof follows from what you wrote above: if a number is rational then its representation is periodic, so non-periodic implies non-rational. --CiaPan (talk) 16:03, 16 August 2020 (UTC)

BTW, it's not true that rational numbers can have several representations. Only some of them have more than one decimal expansion, and then there are exactly two such representations - and both are periodic: one ends with a repeating zero, e.g. 0.1000000..., the other one with repeating nine, as 0.099999.... --CiaPan (talk) 16:09, 16 August 2020 (UTC)

The only reason we know that the Champernowne constant is irrational is that its decimal expansion is non-periodic – by construction.  --Lambiam 17:08, 16 August 2020 (UTC)

Three rational numbers to meet given conditions

I've come across this problem: find three rational numbers whose sum is 6, the sum of whose squares is 12.5 and the sum of whose cubes is 27. My thoughts are that one is an integer and the other two are odd multiples of one half, one of which is negative, but I can't find anything to fit. → 2A00:23C6:AA08:E500:941B:9E25:7D2C:74D6 (talk) 17:34, 16 August 2020 (UTC)

How about 2.5, 1.5, and 2? You are lucky to have a solution in the rationals; the general solution requires solving a cubic equation so in general, you're going to need to take cube roots.--Jasper Deng (talk) 17:46, 16 August 2020 (UTC)

More straightforward than I thought, thanks. My thinking was that for the squares two quarters sum to one half, but for the cubes the only way of making eighths sum to an integer was for one to be negative. Can it be assumed that that is the only rational solution? →2A00:23C6:AA08:E500:941B:9E25:7D2C:74D6 (talk) 19:42, 16 August 2020 (UTC)

Not only that, but it is the only solution.--Jasper Deng (talk) 19:55, 16 August 2020 (UTC)

In general, if you're given that the sum is s, the sum of the squares is t, and the sum of the cubes is u, then the three numbers are the three solutions to:

$6x^{3}-6sx^{2}+3(s^{2}-t)x-(s^{3}-3st+2u.)$

(That may or may not be buried in the Alpha results.) The fact that it's given that the numbers are rational is a hint that you can apply rational factoring methods rather than having to apply the cubic formula. The cube of an odd multiple of 1/2 can be an integer + 1/8, integer + 3/8, integer + 5/8 or integer + 7/8 regardless of the sign the original number. It would be interesting to know if there any other rational solutions to sum = 6, sum of squares = 12.5, sum of cubes = integer. --RDBury (talk) 01:34, 17 August 2020 (UTC)

PS. I'm pretty sure now that the only solutions to sum = 6, sum of squares = 12.5, sum of cubes = integer is the one given, in other words the only integer possible for the sum of cubes is 27. This is true whether or not you assume the numbers are rational. If anyone is interested I'll post my reasoning on this, otherwise I'll leave it an 'exercise for the reader'. --RDBury (talk) 02:21, 17 August 2020 (UTC)

Plotting highly suggests it is the only real solution. The only thing I am not completely sure of is whether there may be other complex solutions, but I doubt it. The direct application of the cubic formula should in principle allow us to prove that.--Jasper Deng (talk) 02:44, 17 August 2020 (UTC)

Indeed, looking at the cubic equation and factoring it in this case shows that there are no non-real solutions and that the only solution is the one given. But surely there's a cleaner way to prove that. Casus irreducibilis would be interesting to consider here (for slightly perturbed values of s, t, u). I'm thinking Galois theory might be useful here: the Galois group of this polynomial should always be a subgroup of S₃ (it is trivial in the case of rational roots and is at most the cyclic group of order 3), and permuting the three rational numbers' variable assignments also is a S₃ symmetry of sorts. There might be a connection.--Jasper Deng (talk) 02:49, 17 August 2020 (UTC)

Maybe we can formalize the argument as follows. All three of the numbers in question are roots of this cubic equation. By the fundamental theorem of algebra there are only three roots, so for more than one solution to be possible, we must have at least one solution that duplicates a root. There is clearly no such solution here by inspection. In the case of a solution with all three numbers the same, clearly this happens only if $s=t=u$. With two numbers the same is the interesting case.--Jasper Deng (talk) 03:54, 17 August 2020 (UTC)

If the triplet $a,b$ and $c$ are the three roots of a cubic polynomial in $x$, it can be written (up to a multiplicative constant) in the form $(x-a)(x-b)(x-c)$, and this factorization is unique (up to permuting the factors). So there can only be one triplet solving the problem – possibly none involving reals only, as when $t<0$ (e.g. for $x^{3}+x$).  --Lambiam 08:04, 17 August 2020 (UTC)

@Lambiam: But how do we know that we must use all the roots?--Jasper Deng (talk) 08:10, 17 August 2020 (UTC)

The formulation above equally applies if, for instance, $a=b$. The coefficients of the polynomial are uniquely determined by $s,t,u$, which in term are determined by the triplet $\{a,b,c\}$, viewed as a multiset. To make the argument more explicit, suppose another triplet $\{a',b',c'\}$ gave rise to the same polynomial $P$, so then we have that $P=(x-a)(x-b)(x-c)=(x-a')(x-b')(x-c')$. We can now appeal to the fact that $P$ is an element of a polynomial ring that is a unique factorization domain.  --Lambiam 09:25, 17 August 2020 (UTC)

Is there a largest possible prime number?

Just courious :D TheFibonacciEffect (talk) 20:07, 16 August 2020 (UTC)

No. See Euclid's theorem. Georgia guy (talk) 20:24, 16 August 2020 (UTC)

Oh, thanks TheFibonacciEffect (talk) 20:25, 16 August 2020 (UTC)

There is, however, a largest known prime number. One can prove larger primes exist, but actually computing them is more difficult. --RDBury (talk) 23:55, 16 August 2020 (UTC)

It is 2^82589933-1. Eventually a larger Mersenne prime might be found; I'm estimating the exponent will be between 82589933 and 121883000. Georgia guy (talk) 23:58, 16 August 2020 (UTC)

The next prime number record holder may well not be a Mersenne prime. Among the ten largest numbers known to be prime only two are Mersenne primes one (10223 × 2^31172165 + 1) is not a Mersenne prime. Up to 2016-01-07 all newly found primes that are among the twenty largest known prime numbers were Mersenne primes. Of the ten found since, also only two are Mersenne primes.  --Lambiam 15:19, 17 August 2020‎ (UTC)