Wikipedia:Reference desk/Archives/Mathematics/2023 September 23

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.

September 23

Number of indistinguishable necklaces

If we wish to count the number of indistinguishable necklaces of length n with k different colours where rotation is only permitted, then what will be the count? The article Necklace gives the count as ${\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}$ but I do not understand why they start i from 1 and not 0. 43.224.172.66 (talk) 03:03, 23 September 2023 (UTC)

Some mathematicians have a blind spot when it comes to including 0 as a natural number. To the rest, there is precisely one necklace with zero beads, regardless of the available colours. The given formula breaks down when $n=0,$ so it is somewhat convenient to ignore this case.  --Lambiam 07:42, 23 September 2023 (UTC)

In this case, something something Pólya's enumeration theorem, something something Burnside's lemma. Basically, the number of equivalent necklaces under rotation is the average number of necklaces fixed under rotations. For rotations $i=1\,...\,n-1$, there are $\gcd(i,n)$ groups of $n/\gcd(i,n)$ positions that must be of equal color when rotating, so assigning a color to each group yields $k^{\gcd(i,n)}$ necklaces fixed under rotation. For the last rotation, the identity rotation, clearly every position is fixed under rotation, so there are $k^{n}$ necklaces there. $\gcd(0,n)=\gcd(n,n)=n$ (which makes sense given that rotating $n$ times is equivalent to the identity rotation) so in reality the sum can either be from $0$ to $n-1$ or $1$ to $n$. There just have to be $n$ total summands because there are $n$ rotations. And of course the final division by $n$ is because we are taking the average. GalacticShoe (talk) 11:34, 23 September 2023 (UTC)

Are there infinitely many primes whose first digit and last digit are both 7?

Are there infinitely many primes whose first digit and last digit are both 7? Generally, give a base b and two digits d1 and d2, where d1 is not 0 and d2 is coprime to b, are there infinitely many primes whose first digit is d1 and last digit is d2, in base b? 61.224.131.153 (talk) 03:27, 23 September 2023 (UTC)

For base 2, the answer is affirmative. I suppose it is open for all other cases.  --Lambiam 07:45, 23 September 2023 (UTC)

For base 3, there are only four types of primes (excluding the prime 3):

1. begin with 1 and end with 1
2. begin with 1 and end with 2
3. begin with 2 and end with 1
4. begin with 2 and end with 2

None of these four types are known to be infinite? Is there a possibility only one or two of them are infinite? 61.224.131.153 (talk) 07:54, 23 September 2023 (UTC)

There are trivially infinitely many primes with first base-3 digit 1. For all $x$, by Bertrand 's postulate, there is at least one prime between $3^{x}$ and $2*3^{x}$, which must necessarily start with base-3 digit 1. GalacticShoe (talk) 11:50, 23 September 2023 (UTC)

In general, there are infinitely many primes starting with any integer $n$ in any base $b$. Based on Bertrand's postulate#Better results, for sufficiently large $k$, there is always a prime between $n*b^{k}$ and $n*b^{k}*(1+1/n)=(n+1)*b^{k}$, which must necessarily start with $n$. Similarly, for any $n$ coprime to base $b$, there are infinitely many primes ending in $n$, courtesy of Dirichlet's theorem. Proving that there are infinitely many primes both starting and ending with certain numbers would probably require some extensive work, possibly combining the two theorems. GalacticShoe (talk) 12:23, 23 September 2023 (UTC)

Dirichlet's theorem on arithmetic progressions implies that there are infinitely many primes ending with any particular string of digits in any particular base, if there are any. For example, consider the arithmetic progression 100d + 77. 100.36.106.199 (talk) 12:33, 24 September 2023 (UTC)

..., if there are at least two.  --Lambiam 13:20, 24 September 2023 (UTC)

2 is the only prime ending with 2 in base 10, thus you must only count the primes not dividing the base. 220.132.230.56 (talk) 04:20, 27 September 2023 (UTC)

Funny enough, while proving that there are infinitely many primes starting and ending with certain numbers seems very difficult, proving that there are infinitely many primes containing some string $A$ and ending with some string $B$ coprime to the base is relatively easy. If we assume otherwise, that there are only finitely many such primes, then the sum of the reciprocals of such primes naturally results in a finite number. Meanwhile, the sum of the reciprocals of all primes not containing $A$ but still ending in $B$ is less than the sum of the reciprocals of all primes not containing $A$ but ending in any other string, a sum which converges (see Kempner series.) This means that, added together, the sum of the reciprocals of all primes ending in $B$ is finite. This directly contradicts Dirichlet's theorem. GalacticShoe (talk) 19:41, 26 September 2023 (UTC)

Well, now I have another problem, is the sum of the reciprocals of all primes starting with A and ending with B in a given base diverges? For example, is the sum of the reciprocals of all primes starting with 7 and ending with 7 in base 10 diverges? I think that this should be easier to proof. 220.132.230.56 (talk) 04:23, 27 September 2023 (UTC)

For base 10, there are 36 types of primes (not counting the primes 2 and 5), in general, for base b, there are A062955(b) types of primes (not counting the primes dividing b), none of these 36 types of prime are known to be infinite? 61.224.131.153 (talk) 08:09, 23 September 2023 (UTC)

As far as we know, the answer is that (apart from base 2) none of these classes is known to be infinite.  --Lambiam 15:41, 23 September 2023 (UTC)

Are these true?

1. 0^0 = 1 (exponentiation)
2. 0! = 1 (factorial)
3. eulerphi(0) = 0 (totient)
4. Phi(0,x) = 1 (cyclotomic polynomial)
5. the sum of all elements in the empty set is 0
6. the product of all elements in the empty set is 1
7. the intersection of all elements in the empty set is the set containing all things
8. the union of all elements in the empty set is the empty set
9. the sup of all elements in the empty set is -infinity
10. the inf of all elements in the empty set is +infinity
11. the gcd of all elements in the empty set is 0
12. the lcm of all elements in the empty set is 1
13. the “smallest prime factor” of 1 is +infinity (and 1 is p-rough number of all p)
14. the “largest prime factor” of 1 is -infinity (and 1 is p-smooth number of all p)
15. 1+2+3+4+… = -1/12 (and thus sigma(0) = -1/12 (sum of divisors))
16. 1+2+4+8+… = -1

I think that all of them are true. 61.224.131.153 (talk) 03:42, 23 September 2023 (UTC)

It depends on definitions, and in many cases the expressions in question are simply undefined or dependent on context. I don't want to get lost in the weeds on every one of these, but it's certainly the case that 0!=1. The union over the empty set is taken to be the empty set. There is no set containing all things; assuming there is one would lead to certain contradictions in set theory, see for example Russell's paradox. To avoid this simply leave the intersection over the empty set as undefined; only define intersections over non-empty sets. Infimum and supremums aren't guaranteed to exist even for non-empty sets so I would leaven them undefined, at least over the reals. For the last two, yes, there are certain summation methods that yield finite expressions for these sums, but they aren't sums in the ordinary sense. Normally it's better to simply think of them as divergent series and to take σ(0) to be an undefined expression. --RDBury (talk) 05:14, 23 September 2023 (UTC)

Both 0^0 are 0! are empty product, and the empty product is 1, right? 61.224.131.153 (talk) 07:54, 23 September 2023 (UTC)

No they are not both empty products. One could easily define 0^n as 42*0*0...*0 with n zeroes - and that is zero if n is 1 or more but 42 when n is zero. 1!= 0!*1 and 1!=1 and from that we get 0!=1. Anyway 0^0 is mostly defined as 1 as described in the article linked to just below but when you're dealing with reals rather than integers things become more complicated NadVolum (talk) 12:12, 23 September 2023 (UTC)

Well, a^0 is empty product for any complex number a including a=0, also in any field with additive identity $\theta$ and multiplicative identity $\epsilon$, $a^{0}=\epsilon$ for every a in the field, including $a=\theta$. 220.132.230.56 (talk) 23:02, 23 September 2023 (UTC)

True, but $0^{x}$ is 0 for any x not equal to 0, so no matter how you define it, some limit is going to break. You define it ultimately using whatever definition is most useful to you. If that definition is based on the empty product, then so be it. GalacticShoe (talk) 23:13, 23 September 2023 (UTC)

No, 0^x is undefined for negative x and complex x. 220.132.230.56 (talk) 02:38, 24 September 2023 (UTC)

According to your definitionm and I think it is the best way. But some consider 1+0i to be the same as 1 and would have 0^(1+0i) be 1. Personally I treat 1 as different from 1+0i or 1.0 NadVolum (talk) 10:53, 24 September 2023 (UTC)

All the more reason to leave 0^0 as whatever is most convenient (or heck, leave it undefined, just as $0^{x}$ is for negative and complex $x$.) Not every definition of it is going to be consistent with each other. Choose whatever suits you. GalacticShoe (talk) 15:59, 24 September 2023 (UTC)

For the first question, see our article Zero to the power of zero.  --Lambiam 08:03, 23 September 2023 (UTC)

Why the largest number which a scientific calculator does not overflow is 10^100, not power of 2?

Why the largest number which a scientific calculator does not overflow is 10^100 (googol), not power of 2? Computers only have “on” and “off” two situations, and the largest number make single-precision floating-point format and double-precision floating-point format not overflow are also powers of 2 (2^127 and 2^1023, respectively), but why the largest number which a scientific calculator does not overflow is power of 10 instead of power of 2? 61.224.131.153 (talk) 04:30, 23 September 2023 (UTC)

who says it is? --jpgordon^{𝄢𝄆𝄐𝄇} 04:33, 23 September 2023 (UTC)

It depends on the calculator, there is no standard "overflow size" unless the makers decide to follow IEEE guidelines. (See IEEE 754.) I was always under the impression that a lot of calculators worked in base 10 natively; that was certainly the case for the old mechanical models. --RDBury (talk) 04:42, 23 September 2023 (UTC)

My HP 20s and HP 35s go higher than 10^100 - I'm not sure how high they will go. I think that since calculators are designed for decimal input and output, and calculation speed is not important, they probably use binary-coded decimal to encode one decimal digit with four (or eight) bits. Bubba73 ^{You talkin' to me?} 06:25, 23 September 2023 (UTC)

But use binary-coded decimal will lose 3/8 of combinations and less economical, why not use the double-precision floating-point format directly? 61.224.131.153 (talk) 07:56, 23 September 2023 (UTC)

Speed and extra bits of precision re not problems for a calculator. Working in decimal gives less funnies that people can complain about. Like that dividing by ten doesn't work exactly in binary but it does work out okay when done by hand. Silly complaints using up their money are the last thing a manufacturer wants. NadVolum (talk) 11:58, 23 September 2023 (UTC)

That's right. People like thing to be right in decimal. I think there was an early HP calculator that gave 2²=3.999. Bubba73 ^{You talkin' to me?} 17:09, 23 September 2023 (UTC)

Ha ha, that's a good one! ;-) Yes there wasn't much space for programs in the early calculators. Chips have got so much cheaper since then. NadVolum (talk) 18:05, 23 September 2023 (UTC)

The HP-35 got all of its functions into 767 instructions (7670 bits). It doesn't have a "square" key, so it must have used logs and exponentials to calculate x^y, and had a rounding error, or did not use enough accuracy. Bubba73 ^{You talkin' to me?} 01:44, 24 September 2023 (UTC)

Dividing by ten doesn't work exactly in binary, but dividing by six also doesn't work exactly in decimal, right? 220.132.230.56 (talk) 22:57, 23 September 2023 (UTC)

Clearly the Babylonians got it right by working in base sixty. AndyTheGrump (talk) 01:48, 24 September 2023 (UTC)

"What Every Computer Scientist Should Know About Floating-Point Arithmetic". I would think a modern cheap scientific calculator would be decimal IEEE 854-1987 (now part of 754) or if they had a general purpose processor computer algebra system with arbitrary precision? fiveby(zero) 12:33, 23 September 2023 (UTC)

Depending on the calculator, it may be a limitation of the format chosen for displaying the output, not of the internal format used for performing the actual calculations. If there are only two digits available on the display for denoting the exponent in scientific notation, +9.999999999E+99 is the largest number that can be displayed.  --Lambiam 08:22, 23 September 2023 (UTC)

that's actually a good answer to an odd question. I imagine the internal overflow value is something a bit greater than 2^332. --jpgordon^{𝄢𝄆𝄐𝄇} 17:11, 23 September 2023 (UTC)

According to the Owner's Handbook for my (c. 1984) HP-15C,

Regardless of the display format, the HP-15C always internally holds each number as a 10-digit mantissa and a two-digit exponent of 10

which presumably explains why

When the result of a calculation ... is a number with a magnitude greater than 9.999999999×10⁹⁹, ... the overflow flag ... is set.

Mitch Ames (talk) 09:24, 25 September 2023 (UTC)

However, computer (and calculator) can only have “on” and “off” situations, thus they can only use base 2 to memorize numbers. 118.170.54.98 (talk) 09:50, 25 September 2023 (UTC)

They don't have to use binary - they can use binary-coded decimal; according to [1] the HP-15C did. Mitch Ames (talk) 11:05, 25 September 2023 (UTC)

Better than binary-coded decimal, there are the IEEE 754 decimal formats. — Vincent Lefèvre (talk) 11:15, 25 September 2023 (UTC)

But double-precision floating-point format is really the best. 220.132.230.56 (talk) 12:27, 25 September 2023 (UTC)

, Well, that depends on several factors. Bubba73 ^{You talkin' to me?} 22:29, 25 September 2023 (UTC)

Although bcd calculations are slower than binary calculations, you save time by not doing decimal to binary and back to decimal conversions before and after every calculation (because calculators update the display after every calculation, while computers only print the final result). Also you save memory by leaving out the binary to decimal and vice versa code. 212.178.135.35 (talk) 13:17, 25 September 2023 (UTC) Martin.

Log and exponential functions

I think this is something I should be able to figure out myself, so I don't want to look up the answer. But, given the definition $\log x=\int _{1}^{x}{dx \over x}$, or alternatively defining exp as the unique solution (with appropriate constants) of ${\dot {x}}=x$, I'd like to prove the basic properties $\log(ab)=\log a+\log b$ and so on. "Prove" means at the level of "intro to real analysis" classes where they try to teach you to be fussy about proofs. I did take one of those classes years ago, but this didn't come up. I was just thinking about it recently: is it difficult? What is the basic direction? No complete answers please. Thanks. 2601:644:8501:AAF0:0:0:0:86EA (talk) 21:28, 23 September 2023 (UTC)

Rgdboer's answer for $\log(ab)=\log(a)+\log(b)$ is excellent, but it may go further than hinting. Hopefully not detracting from his answer, summarizing it as a hint I would say "split the integral." GalacticShoe (talk) 00:36, 24 September 2023 (UTC)

Gregoire de Saint-Vincent noted in 1647 that rectangular hyperbolas are stable under squeeze mapping, so planar areas are preserved not only in the whole plane, but also under the hyperbola. Thus the hyperbolic logarithm developed a century before Euler’s exponential functions a^x.

The correct statement is $\log x=\int _{1}^{x}{\frac {dt}{t}}$ where t is a bound variable.

Here the case a>1 and b>1 is considered first so the areas extend to the right of x=1 and the integral is seen as the area over [1,x] and under the hyperbola xy=1. Using b as squeeze parameter,

$\log a=\int _{1}^{a}{\frac {dt}{t}}=\int _{b}^{ab}{\frac {dt}{t}}.$ Then

$\log b+\log a=\int _{1}^{b}{\frac {dt}{t}}+\int _{b}^{ab}{\frac {dt}{t}}=\int _{1}^{ab}{\frac {dt}{t}}=\log ab.$

The cases where one or both of a, b are in the unit interval are similar when signed areas are noted.— Rgdboer (talk) 00:13, 24 September 2023 (UTC)

Being "fussy about proofs" applies to the basics, defining limits, defining derivatives, defining integrals, the fundamental theorem of calculus, intermediate value theorem, mean value theorem, etc. Once you you've proved them rigorously you can apply them just as you would in freshman calculus. One of the basics is the chain rule and (via FTC) substitution in integration. Another is that you can break up the interval of integration: $\int _{a}^{c}{f(x)dx}=\int _{a}^{b}{f(x)dx}+\int _{b}^{c}{f(x)dx}.$ So the solution give above is rigorous, being an application of facts already proven. (I would have left it at that as enough of a hint. But Wikipedia is not "spoiler free". Maybe if you said it was a homework problem the answer would be more just a hint since we have a "we won't do your homework for you" policy.)

Btw, you can define exp(x) as $\lim _{n\to \infty }(1+{\tfrac {x}{n}})^{n}$. It's a somewhat more practical definition because it gives actual approximate values instead of depending on a "unique solution". (To use the unique solution definition rigorously you'd need to prove that there is a solution and that there is no more than one solution. Actually there is more than one solution to ${\dot {x}}=x$; you probably meant the initial value problem ${\dot {x}}=x,x(0)=1.$ There are theorems which prove the existence and uniqueness of solutions to initial value problems, but the conditions are fiddly. Your intro to analysis course probably didn't cover most, or even any, of them. I'll dig up my copy of Protter and Morrey to see what they did.) You can also define exp(t) using it's series, and in fact that's what is usually done. In that case it's much easier to prove x = exp(t) satisfies ${\dot {x}}=x$. Of course when there are competing definitions you're required to prove that they define the same thing, so there's another challenge for you. --RDBury (talk) 00:58, 24 September 2023 (UTC)

PS. Protter and Morrey define exp as the inverse of ln, the general properties of inverse functions having been covered already. They also give a theorem proving there is a unique solution to an initial value problem under certain conditions, and the proof is an application of facts about contraction mappings in metric spaces. This seems to me to be overkill for the current question. I'll see what else I can find. --RDBury (talk) 01:33, 24 September 2023 (UTC)

Thanks all. I did think about separating the integral into the a part and the b-a part. I'll see what more I can do. The underlying idea is to use exercises like this to get back into "shape" math-wise, if that makes any sense. Yes I'm used to exp being defined as the inverse of log. It just seems ok to also do it the other way. exp' = exp having a unique solution follows from the Picard-Lindelof theorem of course. 2601:644:8501:AAF0:0:0:0:86EA (talk) 20:46, 24 September 2023 (UTC)