login
This site is supported by donations to The OEIS Foundation.

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186646 Every fourth term of the sequence of natural numbers 1,2,3,4,... is halved. 5
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 (list; graph; refs; listen; history; text; internal format)
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.

Equivalence with the definition shown by F. 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)

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

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

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

a(n) = (n/48)*{13*(n mod 4)+7*[(n+1) mod 4]+7*[(n+2) mod 4]+[(n+3) mod 4]}. - Paolo P. Lava, Mar 10 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

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

CROSSREFS

Cf. A000224 (size of the set of moduli of k^2 mod n).

Sequence in context: A019554 A076685 A254503 * A293303 A110500 A161871

Adjacent sequences:  A186643 A186644 A186645 * A186647 A186648 A186649

KEYWORD

nonn,easy,mult

AUTHOR

R. J. Mathar, Feb 25 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 22:27 EDT 2018. Contains 315360 sequences. (Running on oeis4.)