A186646 Every fourth term of the sequence of natural numbers 1,2,3,4,... is halved.

1, 2, 3, 2, 5, 6, 7, 4, 9, 10, 11, 6, 13, 14, 15, 8, 17, 18, 19, 10, 21, 22, 23, 12, 25, 26, 27, 14, 29, 30, 31, 16, 33, 34, 35, 18, 37, 38, 39, 20, 41, 42, 43, 22, 45, 46, 47, 24, 49, 50, 51, 26, 53, 54, 55, 28, 57, 58, 59, 30, 61, 62, 63, 32, 65, 66, 67, 34, 69, 70, 71, 36, 73, 74, 75, 38, 77, 78, 79, 40, 81, 82, 83, 42, 85, 86, 87, 44, 89, 90, 91, 46, 93, 94, 95, 48, 97, 98, 99

Offset: 1

Author

R. J. Mathar, Feb 25 2011

Keywords

• nonn
• easy
• mult

Comments

a(n) is the length of the period of the sequence k^2 mod n, k=1,2,3,4,..., i.e., the length of the period of A000035 (n=2), A011655 (n=3), A000035 (n=4), A070430 (n=5), A070431 (n=6), A053879 (n=7), A070432 (n=8), A070433 (n=9), A008959 (n=10), A070434 (n=11), A070435 (n=12) etc.

From Franklin T. Adams-Watters, Feb 24 2011: (Start)

Clearly if gcd(n,m) = 1, a(nm) = lcm(a(n),a(m)), so it suffices to establish this for prime powers.

If p is a prime, the period must divide p, but k^2 mod p is not constant, so a(p) = p.

a(p^e), e > 1, must be divisible by a(p^(e-1)), and must divide p^e. If p != 2, (p^(e-1)+1)^2 = p^(2e-2)+2p^(e-1)+1 == 2p^(e-1)+1 (mod p^2), so a(p^e) != p^(e-1); it must then be e.

By inspection, a(4) = 2 and a(8) = 4.

This leaves a(2^e), e > 3. But then (2^(e-2)+1)^2 = 2^(2e-4)+2^(e-1)+1 == 2^(e-1)+1 (mod 2^e), so a(n) > 2^(e-2). On the other hand, (2^(e-1)+c)^2 = 2^(2e-2)+c2^e+c^2 == c^2 (mod 2^e). Hence the period is 2^(e-1). (End)

Links

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

Crossrefs

Cf. A000224 (size of the set of moduli of k^2 mod n), A019554, A060819, A061037, A090129, A142705, A164115, A283971.

Programs

Maple

A186646 := proc(n) if n mod 4 = 0 then n/2 ; else n ; end if; end proc ;

Mathematica

Flatten[Table[{n,n+1,n+2,(n+3)/2},{n,1,101,4}]] (* or *) LinearRecurrence[ {0,0,0,2,0,0,0,-1},{1,2,3,2,5,6,7,4},100] (* Harvey P. Dale, May 30 2014 *)
Table[n (7 - (-1)^n - 2 Cos[n Pi/2])/8, {n, 100}] (* Federico Provvedi , Jan 02 2018 *)

PARI

a(n)=if(n%4,n,n/2) \\ Charles R Greathouse IV, Oct 16 2015

Python

def A186646(n): return n if n&3 else n>>1 # Chai Wah Wu, Jan 10 2023

Formula

a(n) = 2*a(n-4) - a(n-8).

a(4n) = 2n; a(4n+1) = 4n+1; a(4n+2) = 4n+2; a(4n+3) = 4n+3.

a(n) = n/A164115(n).

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

Dirichlet g.f.: (1-2/4^s)*zeta(s-1).

A019554(n) | a(n). - Charles R Greathouse IV, Feb 24 2011

a(n) = n*(7 - (-1)^n - (-i)^n - i^n)/8, with i=sqrt(-1). - Bruno Berselli, Feb 25 2011

Multiplicative with a(p^e)=2^e if p=2 and e<=1; a(p^e)=2^(e-1) if p=2 and e>=2; a(p^e)=p^e otherwise. - David W. Wilson, Feb 26 2011

a(n) * A060819(n+2) = A142705(n+1) = A061037(2n+2). - Paul Curtz, Mar 02 2011

a(n) = n - (n/2)*floor(((n-1) mod 4)/3). - Gary Detlefs, Apr 14 2013

a(2^n) = A090129(n+1). - R. J. Mathar, Oct 09 2014

a(n) = n*(7 - (-1)^n - 2*cos(n*Pi/2))/8. - Federico Provvedi, Jan 02 2018

E.g.f.: (1/4)*x*(4*cosh(x) + sin(x) + 3*sinh(x)). - Stefano Spezia, Jan 26 2020

Sum_{k=1..n} a(k) ~ (7/16) * n^2. - Amiram Eldar, Nov 28 2022