cp's OEIS Frontend

A046642 Numbers k such that k and number of divisors d(k) are relatively prime.

%I A046642 #52 Feb 17 2024 11:27:24
%S A046642 1,3,4,5,7,11,13,15,16,17,19,21,23,25,27,29,31,33,35,37,39,41,43,47,
%T A046642 49,51,53,55,57,59,61,64,65,67,69,71,73,77,79,81,83,85,87,89,91,93,95,
%U A046642 97,100,101,103,105,107,109,111,113,115,119,121,123,125,127,129,131
%N A046642 Numbers k such that k and number of divisors d(k) are relatively prime.
%C A046642 Numbers k such that tau(k)^phi(k) == 1 (mod k), where tau(k) is the number of divisors of k (A000005) and phi(k) is the Euler phi function (A000010). - _Michel Lagneau_, Nov 20 2012
%C A046642 Density is at least 4/Pi^2 = 0.405... since A056911 is a subsequence, and at most 1/2 since all even numbers in this sequence are squares. The true value seems to be around 0.4504. - _Charles R Greathouse IV_, Mar 27 2013
%C A046642 They are called anti-tau numbers by Zelinsky (see link) and their density is at least 3/Pi^2 (theorem 57 page 15). - _Michel Marcus_, May 31 2015
%C A046642 From _Amiram Eldar_, Feb 21 2021: (Start)
%C A046642 Spiro (1981) proved that the number of terms of this sequence that do not exceed x is c * x + O(sqrt(x)*log(x)^3), where 0 < c < 1 is the asymptotic density of this sequence.
%C A046642 The odd numbers whose number of divisors is a power of 2 (the odd terms of A036537) are terms of this sequence. Their asymptotic density is A327839/A076214 = 0.4212451116... which is a better lower bound than 4/Pi^2 for the asymptotic density of this sequence.
%C A046642 A better upper limit than 0.5 can be obtained by considering the subsequence of odd numbers whose 3-adic valuation is not of the form 3*k-1 (i.e., odd numbers without those k with gcd(k, tau(k)) = 3), whose asymptotic density is 6/13 = 0.46153...
%C A046642 The numbers of terms not exceeding 10^k, for k = 1, 2, ..., are 5, 49, 459, 4535, 45145, 450710, 4504999, 45043234, 450411577, 4504050401, ... (End)
%H A046642 Reinhard Zumkeller, <a href="/A046642/b046642.txt">Table of n, a(n) for n = 1..10000</a>
%H A046642 Mart Abel, Helena Lauer, and Ellen Redi, <a href="https://doi.org/10.12697/ACUTM.2021.25.07">About the number of τ-numbers relative to polynomials with integer coefficients</a>, Acta Comment. Univ. Tartu. Math. 25, No. 1, 107-117, 2021.
%H A046642 Claudia A. Spiro, <a href="https://www.proquest.com/openview/3c72b874bc57946ce415a828b143fd22/">The Frequency with Which an Integral-Valued, Prime-Independent, Multiplicative or Additive Function of n Divides a Polynomial Function of n</a>, Ph. D. Thesis, University of Illinois, Urbana-Champaign, 1981.
%H A046642 Joshua Zelinsky, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Zelinsky/zelinsky9.html">Tau Numbers: A Partial Proof of a Conjecture and Other Results</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8.
%F A046642 A009191(a(n)) = 1.
%t A046642 Select[ Range[200], CoprimeQ[#, DivisorSigma[0, #]] &] (* _Jean-François Alcover_, Oct 20 2011 *)
%o A046642 (Haskell)
%o A046642 a046642 n = a046642_list !! (n-1)
%o A046642 a046642_list = map (+ 1) $ elemIndices 1 a009191_list
%o A046642 -- _Reinhard Zumkeller_, Aug 14 2011
%o A046642 (PARI) is(n)=gcd(numdiv(n),n)==1 \\ _Charles R Greathouse IV_, Mar 27 2013
%Y A046642 Cf. A000005, A000010, A009191, A009230, A036537, A056911, A076214, A327839.
%K A046642 nonn,nice,easy
%O A046642 1,2
%A A046642 _Labos Elemer_