Wikipedia:Reference desk/Mathematics

From Wikipedia, the free encyclopedia


The Wikipedia Reference Desk covering the topic of mathematics.

Welcome to the mathematics reference desk.
Want a faster answer?

Main page: Help searching Wikipedia

How can I get my question answered?

  • Provide a short header that gives the general topic of the question.
  • Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
  • Post your question to only one desk.
  • Don't post personal contact information – it will be removed. All answers will be provided here.
  • Specific questions, that are likely to produce reliable sources, will tend to get clearer answers,
  • Note:
    • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
    • We don't answer requests for opinions, predictions or debate.
    • We don't do your homework for you, though we’ll help you past the stuck point.
    • We are not a substitute for actually doing any original research required, or as a free source of ideas.



How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

  • The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.
 
Choose a topic:
 
See also:
Help desk
Village pump
Help manual


May 19

Easiest way to tell if a number is in Pascal's Triangle (other than diagonal with every number)?

In other words how easy is to tell whether for a given s whether there exists number n and k so that s = n choose k where s not equal to n (and k =1 or n-1)?Naraht (talk) 11:07, 19 May 2017 (UTC)

I'm pretty sure every natural number is in Pascal's triangle; this is easy to demonstrate as the second row from the edge always increments by one as you move down each row... --Jayron32 11:17, 19 May 2017 (UTC)
That's why I excluded the diagonals that have every number, which is what you are describing.Naraht (talk) 11:27, 19 May 2017 (UTC)
This appears to be OEISA006987. Not that that helps much since the formulas given basically just generate all possibilities and sort. (At least as far as I can tell without diving into the code.) For triangular numbers the test is easy, p is triangular if √(8p+1) is an integer. For higher k you could do a binary search on the range k√(k!p) to k√(k!p)+k-1, which covers the possible values of n. Note that you can assume k≤n/2 to put a bound on k. --RDBury (talk) 13:53, 19 May 2017 (UTC)
Agreed that this is OEISA006987. Not sure I understand the "for higher k", can you give me an example? Also looking at the link to the first thousand gave some *really* interesting values for the last digit among the number in this sequence. Of the first thousand, there are only three entries ending in 7: 1287 (3^2*11*13), 100947 (3*7*11*19*23) and 245157 (3*11*17*19*23) (and only seven ending in 2 and only eight ending in 9) conversely, there are 242 ending in 0. So below roughly 300,000 the chance of a number ending in 7 being in the list is 1 in 100,000 and a number ending in 0 being in this list is roughly 1 in 1000. I know this is tied to (among other things) numbers toward the middle of the table having a *large* numbers of factors (especially factors of 2) (in fact, this should get worse for the odd numbers as things get even bigger since you are looking at the odd numbers representing the area part of a Sierpinski triangle). Not sure why an ending in 2 is so rare.Naraht (talk) 16:23, 19 May 2017 (UTC)
Sierpinski Pascal triangle.svg
It's not too hard to understand the patterns in Pascal's triangle modulo p -- they give Sierpinski-like structures like this picture. --JBL (talk) 18:03, 19 May 2017 (UTC)
Maybe you already know this—it seems to me that no prime number p is in Pascal's triangle excluding the entries (p, p–1) and (p, 1). Every other non-unit entry in row p is >p; every non-unit entry in later rows is the sum of entries in the previous row and hence is >p; and every entry in earlier rows is not divisible by p according to the (s choose i) formula. Loraof (talk) 21:01, 19 May 2017 (UTC)
You can study the prime factorization of s to see of it is a binomial coefficient and find n and k. Count Iblis (talk) 20:38, 20 May 2017 (UTC)
This is very vague -- what does "you can study" mean? --JBL (talk) 21:56, 20 May 2017 (UTC)
I'm pretty sure you could, at least, prove there are no prime numbers of this form. For k=2, suppose a prime p has the form n(n-1)/2. Then p|m(n-1) and since n and n-1 are relatively prime that means p|n or p|n-1. Either way you get p≤n-1, n(n-1)=2p≤2(n-1). p>0 so n>1 and therefore n≤2 and then n=2. But This give p=1 which is not prime. I'm thinking a similar but more elaborate argument would work higher k. It also seems like this has probably already been done so the real problem is to find a sufficiently precise internet search to find it.
As an example of what I was talking about above, I'll find p=100947 as a binomial coefficient. First 8p+1 ends in a 7 and so can't be a square, so you can eliminate k=2. For k=3 you need to solve 6⋅100947=605682=n(n-1)(n-2) so I'll start with the estimate n=3√605682+1≈86. But 86⋅85⋅84=614040 is too big and 85⋅84⋅83=592620 is too small. For k=4 you need to solve 24⋅100947=2422728=n(n-1)(n-2)(n-3) and I'll start with n=4√2422728+1.5≈41. But 41⋅40⋅39⋅38=2430480 is too big and 40⋅39⋅38⋅37=2193360 is too small. Similarly for k=5 I get n=28 is too small and n=29 is too big. For k=6 I get n=22 is too small but n=23 is just right, so the answer is 100947=(23 choose 6). Note that if I had reached k=10 the estimate for n would be 19 which is less than 2k and I could stop by the assumption k≤n/2. --RDBury (talk) 01:16, 21 May 2017 (UTC)
Loraof's post already does this for prime numbers (there is no advantage in going diagonal by diagonal) and your procedure does not use the prime factorization. I am deeply skeptical that if I write down a moderately large number whose factorization involves powers of several primes that Count Iblis could actually produce an n and k. --JBL (talk) 14:14, 21 May 2017 (UTC)
Yep, I missed Loraof's post and it's much more elegant that what I gave, not to mention being valid for all k. Probably the prime factorization could quickly eliminate some cases. For example if you knew the highest prime dividing (n choose k) then you might be able to derive some bounds on n and k. I doubt these would be elementary results though, for example Bertrand's postulate basically states that the highest prime factor of (2k choose k) is larger than k. You could generate some interesting problems as special cases though; one that comes to mind is whether there are an infinite number of triangular numbers of the form paqb. --RDBury (talk) 05:13, 22 May 2017 (UTC)

Let's do a test. I've generated a few random binomials with n and k random integers in the range from 0 to 1000 using a program that doesn't tell me the values of n and k, here they are:

1)

466994284548583803300278769913371600370285173518246621157508592708278631920249039239741521485883159864348314955960097954929138839299479325159518227723 1032648491031918897933092963064896816547242433724442224735677791072510454500

List of prime factors with multiplicities:

{{2, 2}, {3, 4}, {5, 3}, {7, 1}, {11, 1}, {13, 1}, {19, 2}, {23, 1}, {29, 1}, {31, 1}, {37, 1}, {41, 1}, {47, 1}, {53, 1}, {61,1}, {67, 1}, {73, 1}, {83, 1}, {101, 1}, {103, 1}, {107, 1}, {137,1}, {139, 1}, {149, 1}, {151, 1}, {181, 1}, {199, 1}, {211,1}, {223, 1}, {227, 1}, {229, 1}, {233, 1}, {239, 1}, {241, 1}, {251, 1}, {367, 1}, {373, 1}, {397, 1}, {401, 1}, {409,1}, {419, 1}, {421, 1}, {431, 1}, {433, 1}, {439, 1}, {443,1}, {449, 1}, {457, 1},{461, 1}, {463, 1}, {467, 1}, {479, 1}, {487, 1}, {491, 1}, {499, 1}, {503, 1}, {509, 1}, {521, 1}, {523, 1}, {541, 1}, {547, 1}, {557, 1}, {563, 1},{569, 1}, {571, 1}, {577, 1}, {587, 1}, {593, 1}, {599, 1}, {601, 1}, {607, 1}, {613, 1}, {617, 1}, {619, 1}, {631, 1}, {641,1}, {643, 1}, {647, 1},{653, 1}, {659, 1}, {661, 1}, {673, 1}, {677, 1}, {683, 1}, {691, 1}, {701, 1}, {709, 1}, {719, 1}, {727, 1}, {733, 1}, {739, 1}, {743, 1}, {751, 1}}


2)

14219440312894905883456430914716897018371279442018303852092713531704020336124304240597295324573938858767514519886053332637725586394759413114205334877 66163467650204000

List of prime factors with multiplicities:

{{2, 5}, {3, 2}, {5, 3}, {11, 1}, {13, 1}, {17, 2}, {19, 1}, {23, 1}, {37, 1}, {41, 1}, {67, 1}, {89, 1}, {97, 1}, {101, 1}, {103, 1}, {113, 1}, {149, 1}, {151, 1}, {157, 1}, {191, 1}, {193, 1}, {197, 1}, {199, 1}, {223, 1}, {227, 1}, {229, 1}, {233, 1}, {239, 1}, {241, 1}, {251, 1}, {257, 1}, {263, 1}, {269, 1}, {271, 1}, {277, 1}, {281, 1}, {283, 1}, {293, 1}, {307, 1}, {311, 1}, {313, 1}, {443, 1}, {449, 1}, {457, 1}, {461, 1}, {463, 1}, {467, 1}, {479, 1}, {487, 1}, {491, 1}, {499, 1}, {503, 1}, {509, 1}, {521, 1}, {523, 1}, {541, 1}, {547, 1}, {557, 1}, {563, 1}, {569, 1}, {571, 1}, {577, 1}, {587, 1}, {593, 1}, {599, 1}, {601, 1}, {607, 1}, {613, 1}, {617, 1}, {619, 1}}


3)

28526841448966526904814871581376340460641005577527658685892263022158264876030100284136507173013267287855011516467966968035331326424683431284 062065949227012928

List of prime factors with multiplicities:

{{2, 6}, {3, 1}, {7, 1}, {13, 1}, {17, 1}, {29, 1}, {43, 1}, {47, 1}, {53, 1}, {67, 1}, {73, 1}, {79, 1}, {89, 1}, {101, 1}, {113, 1}, {127, 1}, {131, 1}, {137, 1}, {139, 1}, {149, 1}, {151, 1}, {157, 1}, {163, 1}, {167, 1}, {173, 1}, {179, 1}, {181, 1}, {197, 1}, {199, 1}, {211, 1}, {223, 1}, {227, 1}, {263, 1}, {269, 1}, {271, 1}, {277, 1}, {281, 1}, {283, 1}, {293, 1}, {397, 1}, {401, 1}, {409, 1}, {419, 1}, {421, 1}, {431, 1}, {433, 1}, {439, 1}, {443, 1}, {449, 1}, {787, 1}, {797, 1}, {809, 1}, {811, 1}, {821, 1}, {823, 1}, {827, 1}, {829, 1}, {839, 1}, {853, 1}, {857, 1}, {859, 1}, {863, 1}, {877, 1}, {881, 1}, {883, 1}, {887, 1}, {907, 1}}


4)

219124892653192629509031290260537219179031348551685189918337638888845238898171247274479933261751574327696334514108069555125625572415944 5376675

List of prime factors with multiplicities:

{{3, 4}, {5, 2}, {7, 2}, {11, 1}, {17, 1}, {19, 2}, {23, 1}, {31, 1}, {37, 1}, {41, 1}, {47, 1}, {61, 1}, {67, 1}, {71, 1}, {83, 1}, {97, 1}, {107, 1}, {109, 1}, {113, 1}, {163, 1}, {167, 1}, {191, 1}, {193, 1}, {197, 1}, {199, 1}, {211, 1}, {223, 1}, {227, 1}, {229, 1}, {233, 1}, {239, 1}, {241, 1}, {251, 1}, {331, 1}, {337, 1}, {347, 1}, {349, 1}, {353, 1}, {359, 1}, {367, 1}, {373, 1}, {379, 1}, {383, 1}, {389, 1}, {397, 1}, {401, 1}, {409, 1}, {419, 1}, {421, 1}, {431, 1}, {433, 1}, {439, 1}, {443, 1}, {449, 1}, {457, 1}, {461, 1}, {463, 1}, {467, 1}, {479, 1}, {487, 1}, {491, 1}, {499, 1}}

To extract , you can use that you'll find the entire range of prime numbers contained in the interval between n and n-k+1 (when taking k to be smaller than or equal to n/2). You then need to consider the prime numbers generated by factoring the composite numbers in that interval, the largest numbers of the form 2 times a prime number will yield a prime number that won't be canceled by the denominator. So, it's a simple puzzle to solve the problem. Count Iblis (talk) 04:58, 22 May 2017 (UTC)

Like I said, you could probably use the factorization to narrow down the possibilities for n and k and get some likely guesses, but that's a long way from producing an algorithm that's guaranteed to work all the time. Consider 120 = (16 choose 2) = (10 choose 3); you can narrow down the possibilities for n and k to two, but there are more than two solutions so can't always narrow them down to one. To put it another way, you're starting with (n choose k) for which you know there is an n and k and finding the n and k. But can you take a p, say 2400, which is not on the list and prove that it's not (n choose k) with the given constraints? --RDBury (talk) 05:59, 22 May 2017 (UTC)
I think #3 should be the easiest to figure out. The primes listed have a large gap between 449 and 787, so I would expect that all of the primes listed in the top group (787..907) are in the numbers in the top of the resulting fraction, and then simply check above and below that range until you reach a number without its largest factor present.Naraht (talk) 10:33, 22 May 2017 (UTC)
What was the point of printing out the examples if all you were going to do was reassert that it was straightforward? You could have made the evidence-free assertion without making anyone scroll past all those pixels. --JBL (talk) 11:43, 22 May 2017 (UTC)
Homework exercises for Naraht. Count Iblis (talk) 21:09, 22 May 2017 (UTC)
OK, in other words you are just BSing -- you don't have a method, you just think that sometimes you might be able to work it out maybe. That's fine, I guess, but in the future could you be honest about that instead of leaving cryptic comments that don't actually mean anything? --JBL (talk) 01:58, 23 May 2017 (UTC)
The highest prime powers dividing a binomial can be found by simply counting the number of times a prime power divides n and k. If you write out the binomial as the fraction n (n-1)...(n+1-k)/[k (k-1)...1], without simplification, then Floor[k/p] gives you the number of times you encounter a multiple of p in the denominator, but we want to assign a weight of m to factors of p^m. Since p^2 is then counted once while it should be counted twice we then add Floor[k/p^2], and this then corrects the problem for p^2, but p^3 and higher powers are counted twice, so we need to add a term Floor[k/p^3], etc. etc. In the denominator it's more complicated because the consecutive factors don't start at 1 Mod (p^m). This leads to an extra addition of 1 whenever n Mod p^m < k mod p^m. So, the Floor[k/p^m] contributions to the multiplicity of p then cancel between the numerator and denominator, and we're left with the result that the multiplicity of p is the size of the set where
So, in case of the number 2400, the multiplicity of 5 of the prime 2 indicates that n should be at least 32, which raises the question of what happened to 29. We're not allowed to choose k very small (or just below n), and choosing n a lot larger than 32 would shift the "29 problem" to larger primes. Count Iblis (talk) 21:56, 22 May 2017 (UTC)
The number of times n appears in Pascal's triangle is
∞, 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 2, ... (sequence A003016 in the OEIS)
Now a number n does not appear in Pascal's triangle (other than twice in row n) if and only if the nth number in this sequence is 2. This might lead you to something useful. Loraof (talk) 19:16, 23 May 2017 (UTC)
I am just barely comprehending the above suggestions and this may have been obvious, but appearing only twice would be OEISA137905 (the compliment of OEISA006987) which is what most positive integers fall under, and the listing gives a rather simple program for writing this sequence. It's certainly fine for querying small n (easy enough), but it's computationally expensive for it compares n to all entries, thus optimizing algorithm(s) that skip invalid ranges could be added to it. Similarly, optimizing the program used for computing the sequence OEISA006987 is likely better still. Either way, there is additional complexity being added to these algorithms. Of course, these simple heuristic free brute-force search computation methods are often used when the simplicity of implementation is more important than speed.--Modocc (talk) 21:36, 23 May 2017 (UTC)
Speaking of all of this, in (sequence A003015 in the OEIS) there is one very large term. TD Noe says he confirmed that term, which was given by Weger. I don't have Weger's paper, but a website says that Weger's formula gives terms that occur at least 6 times - but not all such terms. How was it confirmed that there are no other terms smaller than the large one? Bubba73 You talkin' to me? 00:39, 24 May 2017 (UTC)

I've been able to solve the problems posted above using the factorization and using Stirling's approximation. For large n and p between 0 and 1 we have:

The largest prime factor R in the binomial and the next prime S defines the possible range [R,S-1] for n. For each element in this set, one can solve (numerically) for p using the above equation for the logarithm of the binomial and equating that to the logarithm of the given number. Multiplying n by p must yield and integer. In the above cases the ranges are small, so you're done pretty fast. But the accuracy is huge so even if the range were to be large, the probability of n p being closer than the numerical error to an integer is negligible. Count Iblis (talk) 02:58, 24 May 2017 (UTC)

May 21

Vertex angles of a convex polyhedron

As JBL mentioned in a recent thread, the sum of the face angles at a particular vertex of a convex polyhedron must be less than 360°. (1) Is there a simple proof of this? (2) Is there a formula for this sum? (Presumably it must depend on the angles between the faces or edges and some reference line.) Loraof (talk) 16:25, 21 May 2017 (UTC)

I suppose that, while not really simple, that may be as simple as it gets (and as far as I can see it only applies when the number of faces meeting at the vertex is 3). I was thinking in terms of an umbrella whose rigid ribs can be viewed as edges of a polyhedron. When you (or the wind) open it all the way so it makes a plane, the sum of the angles at the apex is 360°. On the other hand, if you close it completely so each rigid edge approaches the umbrella's pole, each angle (and hence their sum) approaches 0°. It seems like all the angles between the edge-ribs should be monotonic as you gradually close the umbrella. I have this feeling that a proof of this should be trivial, but I can't come up with it. Loraof (talk) 14:53, 22 May 2017 (UTC)
Here is how I would try to prove it: pick a vertex and choose a direction that points towards the interior of the polyhedron. Show that there is a small number epsilon so that taking a plane slice at distance epsilon in the chosen direction cuts off a pyramid. By construction, this pyramid has the property that the altitude from the apex lands inside the base. Cut the pyramid into tetrahedra, taking the apex, the foot of the altitude, and a pair of consecutive base vertices as the vertices. Then the desired result is the following: in a tetrahedron ABCD such that AB is perpendicular to BCD, angle CAD is smaller in measure than CBD. (Separately, the original argument can be made globally, without considering individual vertices like this -- see angular defect.) --JBL (talk) 15:04, 22 May 2017 (UTC)

May 23

Are there retroreflectors in higher dimensions?

A retroreflector in 1 dimension is a point, in 2-D a right angle works, in 3-D a corner cube works (without needing refraction), do all dimensions have one? Is there always only one per dimension that doesn't need refraction to work? Sagittarian Milky Way (talk) 18:02, 23 May 2017 (UTC)

Assuming that you mean n-dimensional Euclidean space, the answers to your first questions is 'yes': The construction of having one reflecting hyperplane per dimension such that they are all mutually perpendicular works for any number of dimensions; this is a corner of a hypercube. As to the second question, I'm pretty sure there are multiple configurations that could be regarded as retroreflectors, albeit inefficient ones. For example, in two dimensions, consider half of a regular octahedron (four adjacent edges); any ray that reflects off all four of the lines would return antiparallel to the incoming ray. Alternately, also in two dimensions, consider two reflecting lines at 45°; any ray that reflects twice off each line would return in the direction it came from. Though I have not checked the detail, I expect that a five-reflection retroreflector could be constructed in three dimensions, etc. —Quondum 06:01, 24 May 2017 (UTC)

May 24

Irreducibles without primes

Is there an integral domain with an irreducible element but no prime elements? GeoffreyT2000 (talk) 01:26, 24 May 2017 (UTC)

How about ? y and z are irreducible and are obviously not prime. I'm fairly certain there are no prime elements: given a non-unit polynomial , . And by degree considerations, if divides either of these factors, it differs from them by a unit. But counting the parity of the number of occurrences of y rules out that possibility.--2406:E006:332E:1:423:6A72:E875:1DD9 (talk) 05:17, 24 May 2017 (UTC)

Square root of -7 in 2-adic numbers

Does the Ramanujan–Nagell equation give rise to a square root of -7 (= ...111001) in , the 2-adic numbers? GeoffreyT2000 (talk) 01:29, 24 May 2017 (UTC)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Wikipedia:Reference_desk/Mathematics&oldid=781961381"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics
This page is based on the copyrighted Wikipedia article "Wikipedia:Reference desk/Mathematics"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA