| 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
|
| -< 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.
|
| Theorem: Let n be a greenfly, with variety, V, = 2. Suppose that
a_1 is odd. Then:
(i) a_1 = 1 (The only part of this theorem which really requires
some proof.)
(ii) for p_2 = 2, n = 2.M, where M is a Mersenne prime
(iii) for p_2 = 3, p_1 = 2.3^� - 1, where � >= 1 (eg: 5, 17, 53, not
161 (=7*23)).
(iv) for p_2 >= 5, p_1 = 2.t.(p_2)^� - 1, where � >= 1, and
1 =< t =< (p_2 - 1)/2. (eg: for p_2 = 5: p_1 can be 19, 499...)
Questions:
(1) Are there any greenfly with V = 2, with a_1 even?
(2) Are there any greenfly with V >= 3?
|