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

Author

Paolo P. Lava, Apr 19 2017

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A008594, A017593, A108118.

Programs

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 *)

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

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