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,2

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

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

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

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

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

Prog

(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

Crossrefs

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

Sequence in context: A371573 A076685 A254503 * A309108 A308056 A336965

Adjacent sequences: A186643 A186644 A186645 * A186647 A186648 A186649

Keyword

nonn,easy,mult

Author

R. J. Mathar, Feb 25 2011

Status

approved