Mathematics desk
< May 18	<< Apr \| May \| Jun >>	Current desk >

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.

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)[reply]

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... --Jayron 32 11:17, 19 May 2017 (UTC)[reply]

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)[reply]

This appears to be OEIS: A006987. 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)[reply]

Agreed that this is OEIS: A006987. 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)[reply]

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)[reply]

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)[reply]

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)[reply]

This is very vague -- what does "you can study" mean? --JBL (talk) 21:56, 20 May 2017 (UTC)[reply]

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=³√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=⁴√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)[reply]

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)[reply]

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 p^aq^b. --RDBury (talk) 05:13, 22 May 2017 (UTC)[reply]

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 ${\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}$ , 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)[reply]

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)[reply]

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)[reply]

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)[reply]

Homework exercises for Naraht. Count Iblis (talk) 21:09, 22 May 2017 (UTC)[reply]

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)[reply]

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

S_{p}

where

S_{p}=\left\{r|n{\bmod {p}}^{r}<k{\bmod {p}}^{r}\right\}

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)[reply]

From Singmaster's conjecture#Elementary examples:

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)[reply]

I am just barely comprehending the above suggestions and this may have been obvious, but appearing only twice would be OEIS: A137905 (the compliment of OEIS: A006987) 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 OEIS: A006987 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)[reply]

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)[reply]

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:

$\log \left[{\binom {n}{np}}\right]=-n\left[p\log(p)+(1-p)\log(1-p)\right]-{\frac {1}{2}}\log \left[2\pi np(1-p)\right]-{\frac {1}{12n}}\left[{\frac {1}{p}}+{\frac {1}{1-p}}-1\right]+{\frac {1}{360n^{3}}}\left[{\frac {1}{p^{3}}}+{\frac {1}{(1-p)^{3}}}-1\right]\cdots$

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)[reply]