A047432 Numbers that are congruent to {0, 1, 4, 5, 6} mod 8.

0, 1, 4, 5, 6, 8, 9, 12, 13, 14, 16, 17, 20, 21, 22, 24, 25, 28, 29, 30, 32, 33, 36, 37, 38, 40, 41, 44, 45, 46, 48, 49, 52, 53, 54, 56, 57, 60, 61, 62, 64, 65, 68, 69, 70, 72, 73, 76, 77, 78, 80, 81, 84, 85, 86, 88, 89, 92, 93, 94, 96, 97, 100, 101, 102

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

This sequence comprises the only possible sizes of sets of distinct primes for which the sum of their squares is a square. Proof: 2^2 mod 8 = 4, and squares mod 8 of odd numbers are always 1, therefore sums mod 8 of squares of k distinct primes can only be, for k mod 8 = 0..7: {{0, 3}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {0, 5}, {1, 6}, {2, 7}}. But overall, squares mod 8 are always in {0, 1, 4}. These only intersect at k mod 8 in {0, 1, 4, 5, 6}. - Charles L. Hohn, Jul 13 2025

Links

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

Programs

Magma

[n : n in [0..150] | n mod 8 in [0, 1, 4, 5, 6]]; // Wesley Ivan Hurt, Aug 01 2016

Maple

A047432:=n->8*floor(n/5)+[(0, 1, 4, 5, 6)][(n mod 5)+1]: seq(A047432(n), n=0..100); # Wesley Ivan Hurt, Aug 01 2016

Mathematica

Select[Range[0, 100], MemberQ[{0, 1, 4, 5, 6}, Mod[#, 8]] &] (* Wesley Ivan Hurt, Aug 01 2016 *)

PARI

a(n)=[-2,0,1,4,5][n%5+1] + n\5*8 \\ Charles R Greathouse IV, Aug 01 2016

Formula

G.f.: x^2*(1+x)*(2*x^3-x^2+2*x+1) / ( (x^4+x^3+x^2+x+1)*(x-1)^2 ). - R. J. Mathar, Dec 07 2011

From Wesley Ivan Hurt, Aug 01 2016: (Start)

a(n) = a(n-1) + a(n-5) - a(n-6) for n > 6, a(n) = a(n-5) + 8 for n > 5.

a(n) = (40*n - 40 + 3*(n mod 5) + 3*((n+1) mod 5) - 7*((n+2) mod 5) + 3*((n+3) mod 5) - 2*((n+4) mod 5))/25.

a(5k) = 8k-2, a(5k-1) = 8k-3, a(5k-2) = 8k-4, a(5k-3) = 8k-7, a(5k-4) = 8k-8. (End)