[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

346.0. "n dividing n choose k" by TOOLS::STAN () Thu Oct 17 1985 16:10

(N. Robbins)
								n
Define A(n) to be the number of k, 0<k<n, such that n divides  ( ) .
								k

It can be proved that A(n)>=phi(n) where phi(n) is Euler's phi function.

Find all n such that A(n)=phi(n).
T.RTitleUserPersonal
Name
DateLines
346.1TOOLS::STANFri Oct 18 1985 23:00372
It is easy to see that (n choose k) is divisible by n if gcd(n,k)=1.
Since phi(n) is the number of integers below n and relatively prime
to n, we are interested in those cases where n divides (n choose k)
and gcd(n,k)>1.  I list all such cases with k<=n/2 below as n ranges
from 2 to 100.  Those values of n for which A(n)=phi(n) are the values
of n missing from the list, namely:

2,3,4,5,6,7,8,9,11,13,14,15,16,17,19,23,25,27,29,31,32,37,41,43,47,49,
51,53,59,61,62,64,67,71,73,79,81,83,89,91,95,97.

I see no pattern here.

Exceptions: (cases where n choose k is divisible by n and gcd(n,k)>1.)

n= 10  k= 4 
n= 12  k= 6
n= 18  k= 4 
n= 18  k= 8 
n= 20  k= 6 
n= 21  k= 6 
n= 22  k= 8 
n= 22  k= 10 
n= 24  k= 10
n= 26  k= 4 
n= 26  k= 6 
n= 26  k= 12 
n= 28  k= 6
n= 30  k= 9 
n= 30  k= 15 
n= 33  k= 9 
n= 33  k= 12 
n= 33  k= 15 
n= 34  k= 4 
n= 34  k= 6 
n= 34  k= 8 
n= 34  k= 10 
n= 34  k= 12 
n= 34  k= 14
n= 34  k= 16
n= 35  k= 15 
n= 36  k= 8 
n= 36  k= 10 
n= 36  k= 12 
n= 36  k= 14 
n= 36  k= 15 
n= 38  k= 8 
n= 38  k= 10 
n= 38  k= 12 
n= 38  k= 14 
n= 38  k= 16 
n= 38  k= 18 
n= 39  k= 6
n= 39  k= 15 
n= 39  k= 18 
n= 40  k= 12 
n= 40  k= 14 
n= 40  k= 18 
n= 42  k= 4 
n= 42  k= 16 
n= 42  k= 18
n= 42  k= 20 
n= 44  k= 6 
n= 44  k= 14 
n= 44  k= 18
n= 45  k= 21 
n= 46  k= 16 
n= 46  k= 18 
n= 46  k= 20 
n= 46  k= 22
n= 48  k= 15 
n= 48  k= 22
n= 50  k= 4 
n= 50  k= 6 
n= 50  k= 8 
n= 50  k= 12 
n= 50  k= 14 
n= 50  k= 22 
n= 50  k= 24
n= 52  k= 6 
n= 52  k= 10 
n= 52  k= 14 
n= 52  k= 22 
n= 52  k= 24 
n= 54  k= 8 
n= 54  k= 10
n= 54  k= 14 
n= 54  k= 26 
n= 55  k= 10 
n= 55  k= 15 
n= 55  k= 20
n= 56  k= 10 
n= 56  k= 14 
n= 56  k= 21 
n= 56  k= 26 
n= 56  k= 28 
n= 57  k= 6 
n= 57  k= 9 
n= 57  k= 12 
n= 57  k= 15 
n= 57  k= 18 
n= 57  k= 21 
n= 57  k= 24 
n= 58  k= 4 
n= 58  k= 6 
n= 58  k= 12 
n= 58  k= 14
n= 58  k= 20 
n= 58  k= 22 
n= 58  k= 28 
n= 60  k= 9 
n= 60  k= 14 
n= 60  k= 15
n= 60  k= 21 
n= 60  k= 22
n= 63  k= 12 
n= 63  k= 15 
n= 63  k= 21 
n= 63  k= 24
n= 63  k= 28
n= 65  k= 20 
n= 66  k= 4 
n= 66  k= 6 
n= 66  k= 8 
n= 66  k= 10 
n= 66  k= 14 
n= 66  k= 15 
n= 66  k= 16 
n= 66  k= 18 
n= 66  k= 20 
n= 66  k= 21 
n= 66  k= 24 
n= 66  k= 26 
n= 66  k= 28
n= 66  k= 32 
n= 68  k= 6 
n= 68  k= 8 
n= 68  k= 10 
n= 68  k= 12 
n= 68  k= 14 
n= 68  k= 16 
n= 68  k= 18 
n= 68  k= 20
n= 68  k= 22 
n= 68  k= 24 
n= 68  k= 26 
n= 68  k= 28 
n= 68  k= 30 
n= 69  k= 18 
n= 69  k= 21 
n= 69  k= 24
n= 70  k= 8 
n= 70  k= 12 
n= 70  k= 16 
n= 70  k= 18 
n= 70  k= 22 
n= 70  k= 24 
n= 70  k= 26 
n= 70  k= 28 
n= 70  k= 32 
n= 70  k= 34
n= 72  k= 10 
n= 72  k= 14 
n= 72  k= 20 
n= 72  k= 21 
n= 72  k= 22 
n= 72  k= 26 
n= 72  k= 28 
n= 72  k= 34
n= 74  k= 4 
n= 74  k= 6 
n= 74  k= 12 
n= 74  k= 14 
n= 74  k= 16 
n= 74  k= 18 
n= 74  k= 20
n= 74  k= 22 
n= 74  k= 24 
n= 74  k= 26 
n= 74  k= 28 
n= 74  k= 30 
n= 74  k= 32 
n= 74  k= 34 
n= 74  k= 36 
n= 75  k= 6 
n= 75  k= 24
n= 75  k= 33 
n= 76  k= 6 
n= 76  k= 14 
n= 76  k= 16 
n= 76  k= 18 
n= 76  k= 20 
n= 76  k= 22 
n= 76  k= 24 
n= 76  k= 26 
n= 76  k= 28 
n= 76  k= 30
n= 76  k= 34 
n= 77  k= 35 
n= 78  k= 16
n= 78  k= 20 
n= 78  k= 22 
n= 78  k= 28 
n= 78  k= 32 
n= 78  k= 34 
n= 78  k= 38
n= 80  k= 15 
n= 80  k= 18 
n= 80  k= 20 
n= 80  k= 22 
n= 80  k= 26 
n= 80  k= 28 
n= 80  k= 34
n= 80  k= 35 
n= 80  k= 38 
n= 82  k= 4 
n= 82  k= 6 
n= 82  k= 8 
n= 82  k= 10 
n= 82  k= 12
n= 82  k= 14 
n= 82  k= 20 
n= 82  k= 22 
n= 82  k= 24 
n= 82  k= 26 
n= 82  k= 28 
n= 82  k= 30 
n= 82  k= 32 
n= 82  k= 34 
n= 82  k= 36 
n= 82  k= 38 
n= 82  k= 40
n= 84  k= 6 
n= 84  k= 9 
n= 84  k= 10 
n= 84  k= 15 
n= 84  k= 22 
n= 84  k= 24 
n= 84  k= 26 
n= 84  k= 27
n= 84  k= 30 
n= 84  k= 33 
n= 84  k= 34 
n= 84  k= 38 
n= 84  k= 39 
n= 84  k= 40 
n= 84  k= 42 
n= 85  k= 15 
n= 85  k= 20
n= 85  k= 40 
n= 86  k= 8 
n= 86  k= 10 
n= 86  k= 12 
n= 86  k= 14 
n= 86  k= 24 
n= 86  k= 26 
n= 86  k= 28 
n= 86  k= 30 
n= 86  k= 32 
n= 86  k= 34 
n= 86  k= 36 
n= 86  k= 38 
n= 86  k= 40
n= 86  k= 42 
n= 87  k= 9 
n= 87  k= 12 
n= 87  k= 15 
n= 87  k= 18 
n= 87  k= 21 
n= 87  k= 24 
n= 87  k= 27 
n= 87  k= 30 
n= 87  k= 33 
n= 87  k= 36 
n= 87  k= 39 
n= 87  k= 42
n= 88  k= 10 
n= 88  k= 14 
n= 88  k= 26 
n= 88  k= 28 
n= 88  k= 30 
n= 88  k= 34 
n= 88  k= 38 
n= 88  k= 42
n= 90  k= 4 
n= 90  k= 12 
n= 90  k= 14 
n= 90  k= 20 
n= 90  k= 21 
n= 90  k= 22
n= 90  k= 28 
n= 90  k= 32 
n= 90  k= 33 
n= 90  k= 34 
n= 90  k= 38 
n= 90  k= 39 
n= 90  k= 42 
n= 90  k= 44 
n= 90  k= 45
n= 92  k= 6 
n= 92  k= 14 
n= 92  k= 22 
n= 92  k= 30 
n= 92  k= 34
n= 92  k= 38 
n= 92  k= 42 
n= 93  k= 6 
n= 93  k= 15 
n= 93  k= 18 
n= 93  k= 21 
n= 93  k= 24 
n= 93  k= 27 
n= 93  k= 30 
n= 93  k= 33 
n= 93  k= 36
n= 93  k= 39 
n= 93  k= 42 
n= 93  k= 45 
n= 94  k= 32 
n= 94  k= 34 
n= 94  k= 36 
n= 94  k= 38 
n= 94  k= 40
n= 94  k= 42 
n= 94  k= 44 
n= 94  k= 46
n= 96  k= 21 
n= 96  k= 27 
n= 96  k= 33 
n= 96  k= 34 
n= 96  k= 38 
n= 96  k= 39 
n= 96  k= 42 
n= 96  k= 45 
n= 96  k= 46
n= 98  k= 4 
n= 98  k= 6 
n= 98  k= 8 
n= 98  k= 10 
n= 98  k= 12 
n= 98  k= 16 
n= 98  k= 18 
n= 98  k= 20 
n= 98  k= 22 
n= 98  k= 24 
n= 98  k= 26 
n= 98  k= 30 
n= 98  k= 36 
n= 98  k= 38 
n= 98  k= 40 
n= 98  k= 44 
n= 98  k= 46 
n= 98  k= 48
n= 99  k= 21 
n= 99  k= 24 
n= 99  k= 30 
n= 99  k= 39 
n= 99  k= 42 
n= 99  k= 48 
n= 100  k= 6 
n= 100  k= 8 
n= 100  k= 12 
n= 100  k= 14 
n= 100  k= 18
n= 100  k= 22 
n= 100  k= 24 
n= 100  k= 26 
n= 100  k= 28 
n= 100  k= 38 
n= 100  k= 42 
n= 100  k= 44 
n= 100  k= 46 
n= 100  k= 48
346.2HERON::BUCHANANcombinatorial bomb squadMon Jun 04 1990 15:2185
                  -< for a bonus point, why "greenfly" :-) ? >-

	Notation:
		a | b		a divides b
		a \ b		a does not divide b
		(a,b...z)	gcd alias hcf of a,b,...,z
		%		infinity
		[x]		floor(x)


	Let n be a positive integer.

	Define: n is a *greenfly* iff A(n) = phi(n).
	Define: p is a *predator* of n iff p is prime, and p | n.
	Define: n is *eaten* by a predator p if there exists k such that
		(i) n | n-choose-k 
		(ii) p | (n,k)
	(some examples of eating appear in Stan's list of exceptions in -.1)


	Theorem: n is a greenfly iff it is not eaten by any of its predators.

	Proof: easy.


	Theorem: n is not eaten by a predator p, iff it is using one of the two
survival strategies:
	
	(A) 	p^a | n 
	&	n < p^(a+1)

or	(B)	p^2 \ n
	&	p^a | n+p
	&	n < p^(a+1)

	Proof: all much less mysterious than it seems.   Write n and some 
prospective k in base p notation.   Then the critical value:

	sum(i=1->%) [n/p^i] - [k/p^i] - [(n-k)/p^i]

is just the number of carry-figures in the addition of k & (n-k) to form n.
It then becomes natural to pick k = p^a-p, where p^(a+1) > n, and to compare 
the number of carry figures, c, with the number of trailing zeros in n, z.

	c >= z - 1

and equality can only exist (implying survival) by using one of the two
strategies (not mutually exclusive) above.   It can then be shown that these
strategies are successful against all k, not just the particularly dangerous 
value of k chosen above.


	So the problem reduces to one of juggling primes, and the combinatorial
aspects have all disappeared.   Decompose n into prime factors:

		n = product(i=1->V) (p_i)^(a_i)

where p_i are primes, in decreasing order, and all a_i >= 1.   V is the total
number of predators.

	Define: n is *greenish* if
		(i) a_i = 1 for all i > 1, and 
		(ii) p_1 > product(i=2->V) p_i.


	Theorem:   If n is a greenfly, then it is greenish.   If n is greenish
then it is not eaten by its largest predator.

	Proof:	A greenfly can only use Strategy A against its largest 
predator.   Strategy A works against the largest predator exactly in the 
circumstances defined for greenishness.

	Corollary: All prime powers are greenfly.


	So we know all about Strategy A.   The question remaining is which
greenish numbers can successfully wield Strategy B against *all* their lesser 
(= non-largest) predators, and hence achieve greenfly-hood.   I don't think a
prescriptive solution is easy.

	However, there are some obvious lines to explore which generate some
pretty, partial results...

Regards,
Andrew.
346.3more detailsHERON::BUCHANANcombinatorial bomb squadMon Jun 04 1990 16:5619