Refactorable number
Refactorable number
Jump to navigation
Jump to search
A refactorable number or tau number is an integer n that is divisible by the count of its divisors, or to put it algebraically, n is such that τ(n)|n{displaystyle tau (n)|n}. The first few refactorable numbers are listed in (sequence A033950 in the OEIS) as
1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, 84, 88, 96, 104, 108, 128, 132, 136, 152, 156, 180, 184, 204, 225, 228, 232, 240, 248, 252, 276, 288, 296, ...
For example, 18 has 6 divisors (1 and 18, 2 and 9, 3 and 6) and is divisible by 6. There are infinitely many refactorable numbers.
Contents
1 Properties
2 History
3 See also
4 References
Properties[edit]
Cooper and Kennedy proved that refactorable numbers have natural density zero. Zelinsky proved that no three consecutive integers can all be refactorable.[1] Colton proved that no refactorable number is perfect. The equation GCD gcd(n,x)=τ(n){displaystyle gcd(n,x)=tau (n)} has solutions only if n{displaystyle n} is a refactorable number.
Let T(x){displaystyle T(x)} be the number of refactorable numbers which are at most x{displaystyle x}. The problem of determining an asymptotic for T(x){displaystyle T(x)} is open. Spiro has proven that T(x)=xlogx(loglogx)o(1){displaystyle T(x)={frac {x}{{sqrt {log x}}(log log x)^{o(1)}}}}[2]
There are still unsolved problems regarding refactorable numbers. Colton asked if there are there arbitrarily large n{displaystyle n} such that both n{displaystyle n} and n+1{displaystyle n+1} are refactorable. Zelinsky wondered if there exists a refactorable number n0≡amodm{displaystyle n_{0}equiv amod m}, does there necessarily exist n>n0{displaystyle n>n_{0}} such that n{displaystyle n} is refactorable and n≡amodm{displaystyle nequiv amod m}.
History[edit]
First defined by Curtis Cooper and Robert E. Kennedy[3] where they showed that the tau numbers has natural density zero, they were later rediscovered by Simon Colton using a computer program he had made which invents and judges definitions from a variety of areas of mathematics such as number theory and graph theory.[4] Colton called such numbers "refactorable". While computer programs had discovered proofs before, this discovery was one of the first times that a computer program had discovered a new or previously obscure idea. Colton proved many results about refactorable numbers, showing that there were infinitely many and proving a variety of congruence restrictions on their distribution. Colton was only later alerted that Kennedy and Cooper had previously investigated the topic.
See also[edit]
- Divisor function
References[edit]
^ J. Zelinsky, "Tau Numbers: A Partial Proof of a Conjecture and Other Results," Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8
^ Spiro, Claudia (1985). "How often is the number of divisors of n a divisor of n?". Journal of Number Theory. 21 (1): 81–100. doi:10.1016/0022-314X(85)90012-5. Retrieved 4 February 2018..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}
^ Cooper, C.N. and Kennedy, R. E. "Tau Numbers, Natural Density, and Hardy and Wright's Theorem 437." Internat. J. Math. Math. Sci. 13, 383-386, 1990
^ S. Colton, "Refactorable Numbers - A Machine Invention," Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.2
Categories:
- Integer sequences
(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.228","walltime":"0.349","ppvisitednodes":{"value":506,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":79315,"limit":2097152},"templateargumentsize":{"value":38,"limit":2097152},"expansiondepth":{"value":7,"limit":40},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":4900,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 214.971 1 -total"," 68.48% 147.216 1 Template:Cite_journal"," 33.78% 72.619 7 Template:Navbox"," 24.22% 52.076 1 Template:Classes_of_natural_numbers"," 4.43% 9.517 1 Template:Icon"," 2.40% 5.151 1 Template:OEIS"," 1.17% 2.515 1 Template:Nowrap"]},"scribunto":{"limitreport-timeusage":{"value":"0.095","limit":"10.000"},"limitreport-memusage":{"value":2609657,"limit":52428800}},"cachereport":{"origin":"mw1222","timestamp":"20181210084132","ttl":1900800,"transientcontent":false}}});});{"@context":"https://schema.org","@type":"Article","name":"Refactorable number","url":"https://en.wikipedia.org/wiki/Refactorable_number","sameAs":"http://www.wikidata.org/entity/Q2063121","mainEntity":"http://www.wikidata.org/entity/Q2063121","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":"2006-06-08T20:45:22Z","dateModified":"2018-12-10T08:41:35Z","image":"https://upload.wikimedia.org/wikipedia/commons/0/0d/Refactorable_number_Cuisenaire_rods_12.png"}(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgBackendResponseTime":110,"wgHostname":"mw1264"});});