 FACTOID # 20: Statistically, Delaware bears more cost of the US Military than any other state.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Noncototient

A noncototient is a positive integer n that can not be expressed as the difference between a positive integer m and the number of coprime integers below it. That is, m - φ(m) = n, where φ stands for Euler's totient function, has no solution.

It is conjectured that all noncototients are even. This follows from a modified form of the Goldbach conjecture: if the even number n can be represented as a sum of two distinct primes p and q, then pq - φ(pq) = pq - (p - 1)(q - 1) = p + q - 1 = n - 1. It is expected that every even number larger than 6 is a sum of distinct primes, so probably no odd number larger than 5 is a noncototient. The remaining odd numbers are covered by the observations 1 = 2 - φ(2),3 = 9 - φ(9) and 5 = 25 - φ(25).

The first few noncototients are:

10, 26, 34, 50, 52, 58, 86, 100, 116, 122, 130, 134, 146, 154, 170, 172, 186, 202, 206, 218, 222, 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, 518, 520

Erdős and Sierpinski asked whether there exist infinitely many noncototients. This was finally answered in the affirmative by Browkin and Schinzel (1995), who showed every member of the infinite family is an example. Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca. However, it remains unknown whether or not the set of noncototients possesses a positive lower density. Results from FactBites:

 Noncototient - Wikipedia, the free encyclopedia (306 words) A noncototient is a positive integer n that can not be expressed as the difference between a positive integer m and the number of coprime integers below it. The cototient of n is defined as n-φ(n), so a noncototient is a number that is never a cototient. It is conjectured that all noncototients are even.
 Talk:Noncototient - Wikipedia, the free encyclopedia (337 words) But until someone can say for sure which density is referred to and explain it to the others, I've decided to take Primefan's advise and remove the statement. A paper of Banks and Luca at Arxiv math.NT/0409231 shows that the number of noncototients less than X is bounded below by (1/2 + o(1))X/log X [which might well be added to the article --- the Flammenkamp--Luca result gives only a constant multiple of log X as lower bound]. The natural question is thus to ask whether the set of noncototients has positive lower density in the asymptotic sense: that is, whether there is a constant c>0 such that the number of noncototients less than X is infinitely often greater than cX.
More results at FactBites »

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact