OFFSET
1,2
COMMENTS
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
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
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
From Amiram Eldar, Feb 21 2021: (Start)
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.
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.
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...
The numbers of terms not exceeding 10^k, for k = 1, 2, ..., are 5, 49, 459, 4535, 45145, 450710, 4504999, 45043234, 450411577, 4504050401, ... (End)
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Mart Abel, Helena Lauer, and Ellen Redi, About the number of τ-numbers relative to polynomials with integer coefficients, Acta Comment. Univ. Tartu. Math. 25, No. 1, 107-117, 2021.
Claudia A. Spiro, The Frequency with Which an Integral-Valued, Prime-Independent, Multiplicative or Additive Function of n Divides a Polynomial Function of n, Ph. D. Thesis, University of Illinois, Urbana-Champaign, 1981.
Joshua Zelinsky, Tau Numbers: A Partial Proof of a Conjecture and Other Results, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8.
FORMULA
A009191(a(n)) = 1.
MATHEMATICA
Select[ Range[200], CoprimeQ[#, DivisorSigma[0, #]] &] (* Jean-François Alcover, Oct 20 2011 *)
PROG
(Haskell)
a046642 n = a046642_list !! (n-1)
a046642_list = map (+ 1) $ elemIndices 1 a009191_list
-- Reinhard Zumkeller, Aug 14 2011
(PARI) is(n)=gcd(numdiv(n), n)==1 \\ Charles R Greathouse IV, Mar 27 2013
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved