login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085082 Number of distinct prime signatures arising among the divisors of n. 19

%I

%S 1,2,2,3,2,3,2,4,3,3,2,5,2,3,3,5,2,5,2,5,3,3,2,7,3,3,4,5,2,4,2,6,3,3,

%T 3,6,2,3,3,7,2,4,2,5,5,3,2,9,3,5,3,5,2,7,3,7,3,3,2,7,2,3,5,7,3,4,2,5,

%U 3,4,2,9,2,3,5,5,3,4,2,9,5,3,2,7,3,3,3,7,2,7,3,5,3,3,3,11,2,5,5,6,2,4,2,7,4

%N Number of distinct prime signatures arising among the divisors of n.

%C For a squarefree number with n distinct prime divisors, a(n) = n+1.

%C If n = p^r then a(n) = tau(n) = r+1.

%C Question: Find a(n) in the following cases:

%C 1. n = m^k where m is a squarefree number with r distinct prime divisors.

%C 2. n = Product_{i=1..r} (p_i)^i}, where p_i is the i-th distinct prime divisor of n.

%C Answers: 1. (r+k)!/(r!k!). 2. A000108(r+1). - _David Wasserman_, Jan 20 2005

%C I have submitted comments for A000108 and A016098 that each include a combinatorial statement equivalent to the second problem and its solution. - _Matthew Vandermast_, Nov 22 2010

%H Alois P. Heinz, <a href="/A085082/b085082.txt">Table of n, a(n) for n = 1..10000</a>

%e a(30) = 4 and the divisors with distinct prime signatures are 1, 2, 6 and 30. The divisors 3 and 5 with the same prime signature as of 2 and the divisors 10 and 15 with the same prime signature as that of 6 are not counted.

%e The divisors of 36 are 1, 2, 3, 4, 6, 9, 12 and 36. We can group them as (1), (2, 3), (6), (4, 9), (12, 18), (36) so that every group contains divisors with the same prime signature and we have a(36) = 6.

%p with(numtheory):

%p a:= n-> nops({seq(sort(map(x->x[2], ifactors(d)[2])), d=divisors(n))}):

%p seq(a(n), n=1..120); # _Alois P. Heinz_, Jun 12 2012

%t ps[1] = {}; ps[n_] := FactorInteger[n][[All, 2]] // Sort; a[n_] := ps /@ Divisors[n] // Union // Length; Array[a, 120] (* _Jean-Fran├žois Alcover_, Jun 10 2015 *)

%o (PARI) a(n)=my(f=vecsort(factor(n)[,2]),v=[1],s); for(i=1,#f, s=0; v=vector(f[i]+1,i, if(i<=#v, s+=v[i]); s)); vecsum(v) \\ _Charles R Greathouse IV_, Feb 03 2017

%Y Cf. A000108.

%Y The second problem describes A076954(i). See also A006939.

%K easy,nonn

%O 1,2

%A _Amarnath Murthy_, Jul 01 2003

%E More terms from _David Wasserman_, Jan 20 2005

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 07:50 EST 2018. Contains 299599 sequences. (Running on oeis4.)