A070296

[Hans Havermann]

> ID Number: A070296

> Sequence:  2,3,2,2,3,3

> Name:      Let sphi(k) = number of primes less than k and co-prime to it; then
> a(n) = number of integers m with sphi(m) = n.

> Comments:  The (n+1)'th prime contributes a count to a(n). A number with k
> prime factors which lies between n'th(<=) and (n+1)'th prime contributes a
> count to a(n-k).

> Example:   a(4) = 3. The three values of m for which sphi(m) = 4 are 11,14 and
> 15. The coprime , primes less than 11 are 2,3,5, and 7. The coprime, primes
> less than 14 are 3,5,11,and 13. The coprime ,primes less than 15 are
> 2,7,11,and 13.

> Keywords:  more,nonn
> Offset:    0
> Author(s): Amarnath Murthy (amarnath_murthy at yahoo.com), May 10 2002


Here's what I've tried:

p=Prime[Range[1000]]; q=Table[PrimePi[i],{i,1,1000}];

t=Table[c=0;Do[If[GCD[p[[j]],i]==1,c++],{j,1,q[[i-1]]}];c,{i,2,950}]

**I think this is sphi(k), beginning with k=2.**

{0, 1, 1, 2, 1, 3, 3, 3, 2, 4, 3, 5, 4, 4, 5, 6, 5, 7, 6, 6, 6, 8, 7, 8, 7,
8, 7, 9, 7, 10, 10, 9, 9, 9, 9, 11, 10, 10, 10, 12, 10, 13, 12, 12, 12, 14,
13, 14, 13, 13, 13, 15, 14, 14, 14, 14, 14, 16, 14, 17, 16, 16, 17, 16, 15,
18, 17, 17, 16, 19, 18, 20, 19, 19, 19, 19, 18, 21, 20, 21, 20, 22, 20, 21,
21, 21, 21, 23, 21, 22, 22, 22, 22, 22, 22, 24, 23, 23, 23, 25, 23, 26, 25,
24, 25, 27, 26, 28, 26, 27, 27, 29, 27, 28, 28, 28, 28, 28, 27, 29, 28, 28,
28, 29, 27, 30, 30, 29, 28, 31, 29, 30, 30, 30, 30, 32, 30, 33, 31, 32, 32,
32, 32, 32, 32, 32, 32, 34, 32, 35, 34, 34, 33, 34, 33, 36, 35, 35, 35, 35,
35, 37, 36, 35, 36, 38, 36, 38, 36, 37, 37, 39, 37, 38, 38, 38, 38, 40, 38,
41, 39, 40, 40, 40, 39, 40, 40, 40, 39, 42, 41, 43, 42, 41, 42, 44, 42, 45,
44, 44, 44, 44, 43, 44, 44, 44, 44, 44, 42, 46, 45, 45, 45, 45, 45, 45, 45,
45, 44, 45, 44, 47, 46, 46, 46, 48, 46, 49, 47, 47, 48, 50, 48, 49, 49, 49,
48, 51, 49, 52, 51, 52, 51, 51, 50, 51, 51, 51, 51, 53, 51, 52, 52, 51, 53,
54, 52, 53, 52, 53, 53, 55, 53, 54, 53, 54, 54, 56, 54, 57, 56, 55, 56, 56,
55, 58, 57, 57, 56, 59, 57, 60, 59, 58, 58, 59, 59, 60, 58, 59, 59, 61, 59,
60, 60, 60, 60, 60, 59, 60, 60, 60, 60, 60, 59, 62, 60, 61, 60, 63, 61, 64,
63, 62, 63, 65, 63, 64, 64, 64, 63, 64, 64, 64, 64, 64, 64, 64, 62, 66, 65,
65, 65, 65, 64, 67, 66, 66, 65, 66, 65, 67, 66, 65, 66, 68, 66, 69, 67, 68,
68, 70, 68, 69, 69, 68, 69, 71, 69, 71, 70, 70, 69, 70, 69, 72, 71, 71, 70,
71, 70, 73, 71, 72, 72, 72, 71, 74, 72, 73, 73, 75, 74, 73, 74, 74, 74, 76,
73, 75, 75, 75, 75, 75, 74, 77, 76, 75, 76, 78, 76, 77, 77, 77, 76, 77, 76,
79, 77, 78, 78, 78, 77, 78, 78, 78, 77, 80, 77, 81, 80, 80, 80, 80, 79, 80,
80, 79, 79, 82, 81, 83, 81, 81, 82, 82, 81, 84, 82, 83, 82, 85, 83, 84, 84,
84, 84, 86, 84, 85, 85, 85, 85, 84, 84, 87, 86, 86, 85, 88, 85, 89, 88, 87,
88, 90, 88, 89, 88, 89, 89, 89, 88, 89, 88, 89, 89, 91, 89, 90, 90, 89, 90,
90, 90, 92, 91, 91, 90, 93, 91, 92, 91, 91, 92, 92, 91, 94, 93, 93, 93, 95,
93, 94, 93, 94, 94, 96, 93, 95, 96, 95, 95, 95, 94, 95, 94, 95, 94, 97, 95,
98, 97, 96, 97, 97, 96, 98, 96, 97, 96, 97, 96, 97, 97, 97, 97, 97, 96, 99,
98, 98, 98, 98, 96, 100, 99, 99, 98, 99, 98, 99, 99, 98, 99, 101, 99, 100,
99, 99, 100, 102, 100, 101, 101, 101, 101, 103, 100, 104, 102, 103, 102,
103, 103, 105, 104, 104, 103, 104, 103, 104, 104, 103, 104, 106, 104, 105,
104, 105, 105, 107, 105, 105, 106, 106, 105, 108, 106, 109, 107, 108, 108,
108, 107, 110, 109, 108, 108, 109, 108, 111, 110, 109, 109, 112, 110, 113,
111, 112, 112, 112, 111, 113, 112, 111, 112, 112, 110, 114, 113, 113, 113,
113, 112, 113, 112, 113, 113, 115, 113, 116, 114, 114, 114, 117, 116, 116,
115, 115, 116, 118, 116, 117, 117, 117, 116, 119, 116, 120, 119, 118, 119,
118, 118, 119, 119, 119, 118, 119, 118, 121, 120, 120, 120, 122, 120, 121,
120, 121, 120, 123, 121, 122, 122, 122, 122, 122, 120, 124, 123, 122, 123,
123, 122, 123, 123, 123, 122, 125, 123, 124, 124, 123, 124, 124, 123, 126,
124, 125, 125, 125, 123, 124, 125, 125, 125, 127, 125, 126, 126, 126, 126,
126, 125, 128, 126, 128, 126, 127, 126, 129, 128, 127, 128, 128, 127, 130,
128, 128, 128, 131, 129, 130, 130, 130, 129, 130, 129, 132, 131, 131, 130,
131, 130, 133, 132, 131, 131, 134, 132, 133, 133, 132, 133, 133, 133, 135,
132, 134, 134, 136, 134, 135, 135, 134, 135, 135, 133, 135, 134, 135, 135,
135, 134, 137, 136, 136, 135, 136, 135, 136, 136, 135, 136, 138, 135, 137,
137, 137, 137, 137, 136, 136, 136, 137, 137, 139, 137, 140, 138, 139, 138,
139, 138, 139, 139, 138, 138, 141, 139, 142, 141, 140, 140, 143, 141, 144,
142, 143, 143, 143, 142, 143, 142, 143, 143, 145, 142, 145, 144, 144, 144,
144, 143, 144, 144, 144, 143, 144, 143, 146, 144, 144, 145, 147, 144, 148,
146, 146, 147, 149, 148, 148, 148, 148, 147, 148, 146, 148, 148, 148, 147,
148, 147, 150, 149, 149, 148, 151, 149, 152, 150, 150, 151, 153, 151, 152,
151, 152, 152, 152, 151, 152, 152, 151, 152, 152, 151, 152, 151, 151, 152,
152, 151, 154, 153, 153, 151, 155, 153, 154, 154, 153, 154, 154, 153, 156,
154, 155, 155, 155, 153, 155, 155, 155, 155, 157, 154, 156, 156, 156, 156,
155, 155, 158, 156, 157, 156, 159, 157, 158, 158, 157, 157, 160, 158, 159,
158}

Table[Count[t,i],{i,0,150}]

{1, 3, 2, 4, 3, 3, 4, 5, 3, 5, 6, 1, 4, 5, 8, 2, 5, 4, 3, 5, 4, 7, 7, 5, 2,
3, 3, 6, 10, 5, 7, 2, 10, 3, 4, 7, 5, 4, 7, 4, 7, 3, 5, 2, 12, 10, 5, 3, 4,
5, 2, 10, 6, 7, 5, 3, 5, 4, 4, 9, 14, 3, 3, 5, 12, 8, 7, 3, 5, 7, 6, 7, 5,
5, 6, 7, 6, 9, 7, 4, 7, 5, 5, 3, 8, 7, 3, 2, 7, 10, 7, 7, 4, 7, 7, 8, 9, 11,
9, 10, 5, 5, 3, 7, 9, 7, 4, 3, 7, 5, 4, 4, 9, 10, 4, 3, 7, 4, 6, 7, 8, 4, 9,
11, 7, 9, 9, 4, 8, 4, 7, 6, 5, 7, 7, 13, 10, 9, 6, 6, 3, 3, 5, 10, 12, 3, 4,
5, 11, 4, 3}

If we define sphi(1) = 0 (I'm not sure we should), then the first term in
the above matches the author's '2'. The fourth term however does not match.
Or did I miss something?



MIME-Version: 1.0