A285440 Consider the sums of the numbers < n that share the same greatest common divisor with n. Sequence lists numbers that have only one of those sums equal to n.

3, 4, 8, 9, 15, 16, 20, 21, 27, 28, 32, 33, 39, 40, 44, 45, 51, 52, 56, 57, 63, 64, 68, 69, 75, 76, 80, 81, 87, 88, 92, 93, 99, 100, 104, 105, 111, 112, 116, 117, 123, 124, 128, 129, 135, 136, 140, 141, 147, 148, 152, 153, 159, 160, 164, 165, 171, 172, 176, 177

Offset

1,1

Comments

Numbers with no sum equal to n are listed in A108118, with two sums equal to n are listed in A017593 and with three sums equal to n in A008594.

First difference has period 4: {1,4,1,6}.

Numbers that are congruent to {3, 4, 8, 9} mod 12. - Amiram Eldar, Dec 31 2021

Links

Table of n, a(n) for n=1..60.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Formula

From Chai Wah Wu, Nov 01 2018: (Start)

a(n) = a(n-1) + a(n-4) - a(n-5) for n > 5.

G.f.: x*(3*x^4 + x^3 + 4*x^2 + x + 3)/(x^5 - x^4 - x + 1). (End)

Sum_{n>=1} (-1)^(n+1)/a(n) = (3-sqrt(3))*Pi/36. - Amiram Eldar, Dec 31 2021

Example

20 is in the sequence because:
gcd(k,20) = 1 for k = 1, 3, 7, 9, 11, 13, 17, 19: sum is 80.
gcd(k,20) = 2 for k = 2, 6, 14, 18: sum is 40.
gcd(k,20) = 4 for k = 4, 8, 12, 16: sum is 40.
gcd(k,20) = 5 for k = 5, 15: sum is 20.
gcd(k,20) = 10 for k = 10: sum is 10.

Maple

P:=proc(q) local a, k, n, t;
for n from 1 to q do a:=array(1..n-1); for k from 1 to n-1 do a[k]:=0; od;
for k from 1 to n-1 do a[gcd(n, k)]:=a[gcd(n, k)]+k; od; t:=0;
for k from 1 to n-1 do if a[k]=n then t:=t+1; fi; od; if t=1 then print(n); fi;
od; end: P(10^6);

Mathematica

Flatten@ Position[#, k_ /; Length@ k == 1] &@ Table[Select[Transpose@ {Values@ #, Keys@ #} &@ Map[Total, PositionIndex@ Map[GCD @@ {n, #} &, Range[n - 1]]], First@ # == n &][[All, -1]], {n, 180}] (* Michael De Vlieger, Apr 28 2017, Version 10 *)
LinearRecurrence[{1, 0, 0, 1, -1}, {3, 4, 8, 9, 15}, 60] (* Amiram Eldar, Dec 31 2021 *)

Prog

(PARI) a(n) = n--; [3, 4, 8, 9][n%4+1] + 12*(n\4) \\ David A. Corneth, Apr 28 2017
(PARI) is(n) = {my(d=divisors(n), map=vector(d[#d-1]), v=vector(#d-1)); for(i=1, #d-1, map[d[i]]=i); for(i=1, n-1, v[map[gcd(i, n)]]+=i); sum(i=1, #v, v[i]==n)==1} \\ David A. Corneth, Apr 28 2017
(PARI) is(n) = vecsort(concat([3, 4, 8, 9], [n%12]), , 8)==[3, 4, 8, 9] \\ David A. Corneth, Apr 28 2017

Crossrefs

Cf. A008594, A017593, A108118.

Sequence in context: A046974 A177986 A186775 * A135276 A058074 A319875

Adjacent sequences: A285437 A285438 A285439 * A285441 A285442 A285443

Keyword

nonn,easy

Author

Paolo P. Lava, Apr 19 2017

Status

approved