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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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

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

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 November 21 16:27 EST 2017. Contains 295003 sequences.