Consider this function:
F(n, p) =
nC
p - ⌊n/p⌋
where n is a positive integer and p is a prime number.
Is F(n, p) always divisible by p?
If so, prove it.
If not, provide a counterexample.
Notes: nCp is the number of combinations of n elements taken p at a time. It is also known as Binomial Coefficient and read as "n choose p".
• ⌊m⌋ is equal to floor of m which is the greatest integer less than or equal to m
[Edit: this comment is incorrect due to rounding error; see Charlie's note. The comb(61,23) ends in 700 rather than 696.
Thus I do not have a counterexample which disproves the conjecture]
F(61, 23) is the first failure of the conjecture. [incorrect]
F(61, 23) = 37539612570341696 - 2 = 37539612570341694
but 37539612570341694 / 23 = 1632157068275725.8
----
def isprime(n):
'''check if integer n is a prime'''
n = abs(int(n))
if n < 2:
return False
if n == 2:
return True
if not n & 1:
return False
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
primes = [p for p in range(100000) if isprime(p)]
def fact(n):
if n == 1 or n == 0:
return 1
ans = 1
for i in range(n):
ans *= (i+1)
return ans
factorials = [fact(i) for i in range(1000)]
def myComb(m,a):
""" combination m things a at a time """
a = min(a, m-a)
num = 1
# den = 1
for i in range(a):
num *= (m-i)
# den *= (i+1)
return int(num/factorials[a]) # use this if you make a list factorials
# return int(num/fact(a))
# F(n, p) = nCp - ⌊n/p⌋
def f(n,p):
return myComb(n,p) - int(n/p)
big = 65
for n in range(2,big):
smallprimes = []
for s in primes:
smallprimes.append(s)
if s > n:
break
for p in smallprimes:
x = f(n,p)
if (x)%p != 0:
print(n,p,x, (x)%p, x/p)
Edited on June 3, 2023, 3:26 pm
|
|
Posted by Larry
on 2023-06-03 08:33:34 |
Computer solution
