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
(In reply to
Computer solution by Larry)
clearvars,clc
pr=primes(1000);
for n=sym(1:100)
for ps=1:n
p=pr(ps);
if p>=n
break
end
F=nchoosek(n,p)-floor(n/p);
if mod(F,p)~=0
disp([n,p])
end
end
end
found no counterexamples
>> n=sym(61),p=sym(23)
n =
61
p =
23
>> num=factorial(n)
num =
507580213877224798800856812176625227226004528988036003099405939480985600000000000000
>> C=(factorial(n)/(factorial(p)*factorial(n-p)))
C =
37539612570341700
>> (C-floor(n/p))
ans =
37539612570341698
>> ans/p
ans =
1632157068275726
which is an integer rather than a fraction.
Somewhere in your calculations there must have been some floating point that limited accuracy to double precision.
|
|
Posted by Charlie
on 2023-06-03 12:07:38 |
re: Computer solution
