A046642 - OEIS

%I #52 Feb 17 2024 11:27:24

%S 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 49,51,53,55,57,59,61,64,65,67,69,71,73,77,79,81,83,85,87,89,91,93,95,

%U 97,100,101,103,105,107,109,111,113,115,119,121,123,125,127,129,131

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

%C 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 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 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 From _Amiram Eldar_, Feb 21 2021: (Start)

%C 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 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 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 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 Reinhard Zumkeller, <a href="/A046642/b046642.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 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 A009191(a(n)) = 1.

%t Select[ Range[200], CoprimeQ[#, DivisorSigma[0, #]] &] (* _Jean-François Alcover_, Oct 20 2011 *)

%o (Haskell)

%o a046642 n = a046642_list !! (n-1)

%o a046642_list = map (+ 1) $ elemIndices 1 a009191_list

%o -- _Reinhard Zumkeller_, Aug 14 2011

%o (PARI) is(n)=gcd(numdiv(n),n)==1 \\ _Charles R Greathouse IV_, Mar 27 2013

%Y Cf. A000005, A000010, A009191, A009230, A036537, A056911, A076214, A327839.

%K nonn,nice,easy

%O 1,2

%A _Labos Elemer_