Highly totient number
Highly totient number
Jump to navigation
Jump to search
A highly totient number k is an integer that has more solutions to the equation φ(x) = k, where φ is Euler's totient function, than any integer below it. The first few highly totient numbers are
1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440 (sequence A097942 in the OEIS), with 1, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54, and 72 totient solutions respectively. The sequence of highly totient numbers is a subset of the sequence of smallest number k with exactly n solutions to φ(x) = k.[1]
The totient of a number x, with prime factorization x=∏ipiei{displaystyle x=prod _{i}p_{i}^{e_{i}}}
- ϕ(x)=∏i(pi−1)piei−1.{displaystyle phi (x)=prod _{i}(p_{i}-1)p_{i}^{e_{i}-1}.}
Thus, a highly totient number is a number that has more ways of being expressed as a product of this form than does any smaller number.
The concept is somewhat analogous to that of highly composite numbers, and in the same way that 1 is the only odd highly composite number, it is also the only odd highly totient number (indeed, the only odd number to not be a nontotient). And just as there are infinitely many highly composite numbers, there are also infinitely many highly totient numbers, though the highly totient numbers get tougher to find the higher one goes, since calculating the totient function involves factorization into primes, something that becomes extremely difficult as the numbers get larger.
Contents
1 Example
2 Table
3 See also
4 References
Example[edit]
There are five numbers (15, 16, 20, 24, and 30) whose totient number is 8. No positive integer smaller than 8 has as many such numbers, so 8 is highly totient.
Table[edit]
n | ks such that ϕ(k)=n{displaystyle phi (k)=n}  (sequence A032447 in the OEIS) | number of ks such that ϕ(k)=n{displaystyle phi (k)=n} (sequence A014197 in the OEIS) |
| 0 | 0 | |
1 | 1, 2 | 2 |
2 | 3, 4, 6 | 3 |
| 3 | 0 | |
4 | 5, 8, 10, 12 | 4 |
| 5 | 0 | |
| 6 | 7, 9, 14, 18 | 4 |
| 7 | 0 | |
8 | 15, 16, 20, 24, 30 | 5 |
| 9 | 0 | |
| 10 | 11, 22 | 2 |
| 11 | 0 | |
12 | 13, 21, 26, 28, 36, 42 | 6 |
| 13 | 0 | |
| 14 | 0 | |
| 15 | 0 | |
| 16 | 17, 32, 34, 40, 48, 60 | 6 |
| 17 | 0 | |
| 18 | 19, 27, 38, 54 | 4 |
| 19 | 0 | |
| 20 | 25, 33, 44, 50, 66 | 5 |
| 21 | 0 | |
| 22 | 23, 46 | 2 |
| 23 | 0 | |
24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
| 25 | 0 | |
| 26 | 0 | |
| 27 | 0 | |
| 28 | 29, 58 | 2 |
| 29 | 0 | |
| 30 | 31, 62 | 2 |
| 31 | 0 | |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
| 33 | 0 | |
| 34 | 0 | |
| 35 | 0 | |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
| 37 | 0 | |
| 38 | 0 | |
| 39 | 0 | |
| 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
| 41 | 0 | |
| 42 | 43, 49, 86, 98 | 4 |
| 43 | 0 | |
| 44 | 69, 92, 138 | 3 |
| 45 | 0 | |
| 46 | 47, 94 | 2 |
| 47 | 0 | |
48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
| 49 | 0 | |
| 50 | 0 |
See also[edit]
- Highly cototient number
References[edit]
^ Sloane, N. J. A. (ed.). "Sequence A097942 (Highly totient numbers: each number k on this list has more solutions to the equation phi(x) = k than any preceding k (where phi is Euler's totient function, A000010))". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
- L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath
Totient function | |
|---|---|
|
Classes of natural numbers | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Powers and related numbers |
| ||||||||||||||||||||
| Of the form a × 2b ± 1 |
| ||||||||||||||||||||
| Other polynomial numbers |
| ||||||||||||||||||||
Recursively defined numbers |
| ||||||||||||||||||||
| Possessing a specific set of other numbers |
| ||||||||||||||||||||
| Expressible via specific sums |
| ||||||||||||||||||||
| Generated via a sieve |
| ||||||||||||||||||||
Code related |
| ||||||||||||||||||||
| Figurate numbers |
| ||||||||||||||||||||
| Pseudoprimes |
| ||||||||||||||||||||
| Combinatorial numbers |
| ||||||||||||||||||||
| Arithmetic functions |
| ||||||||||||||||||||
| Dividing a quotient | |||||||||||||||||||||
| Other prime factor or divisor related numbers |
| ||||||||||||||||||||
| Recreational mathematics |
| ||||||||||||||||||||
 Mathematics portal | |||||||||||||||||||||
Categories:
- Integer sequences
(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.252","walltime":"0.341","ppvisitednodes":{"value":598,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":86276,"limit":2097152},"templateargumentsize":{"value":645,"limit":2097152},"expansiondepth":{"value":8,"limit":40},"expensivefunctioncount":{"value":0,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":3055,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 190.898 1 -total"," 61.07% 116.576 1 Template:Reflist"," 57.11% 109.013 1 Template:Cite_OEIS"," 50.39% 96.198 1 Template:Cite_web"," 43.69% 83.407 8 Template:Navbox"," 22.28% 42.532 1 Template:Classes_of_natural_numbers"," 12.73% 24.299 1 Template:Totient"," 5.53% 10.548 1 Template:Icon"," 2.66% 5.086 3 Template:OEIS"," 1.97% 3.752 2 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.091","limit":"10.000"},"limitreport-memusage":{"value":2588361,"limit":52428800}},"cachereport":{"origin":"mw1266","timestamp":"20181202035848","ttl":1900800,"transientcontent":false}}});});{"@context":"https://schema.org","@type":"Article","name":"Highly totient number","url":"https://en.wikipedia.org/wiki/Highly_totient_number","sameAs":"http://www.wikidata.org/entity/Q2071769","mainEntity":"http://www.wikidata.org/entity/Q2071769","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png"}},"datePublished":"2004-09-09T21:09:56Z","dateModified":"2018-03-27T03:30:01Z"}(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgBackendResponseTime":90,"wgHostname":"mw1253"});});
