|
%I #109 Dec 12 2023 07:45:26
%S 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,
%T 27,14,29,30,31,16,33,34,35,18,37,38,39,20,41,42,43,22,45,46,47,24,49,
%U 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
%N Every fourth term of the sequence of natural numbers 1,2,3,4,... is halved.
%C 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.
%C From _Franklin T. Adams-Watters_, Feb 24 2011: (Start)
%C Clearly if gcd(n,m) = 1, a(nm) = lcm(a(n),a(m)), so it suffices to establish this for prime powers.
%C If p is a prime, the period must divide p, but k^2 mod p is not constant, so a(p) = p.
%C 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.
%C By inspection, a(4) = 2 and a(8) = 4.
%C 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)
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,2,0,0,0,-1).
%F a(n) = 2*a(n-4) - a(n-8).
%F a(4n) = 2n; a(4n+1) = 4n+1; a(4n+2) = 4n+2; a(4n+3) = 4n+3.
%F a(n) = n/A164115(n).
%F 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 ).
%F Dirichlet g.f.: (1-2/4^s)*zeta(s-1).
%F A019554(n) | a(n). - _Charles R Greathouse IV_, Feb 24 2011
%F a(n) = n*(7 - (-1)^n - (-i)^n - i^n)/8, with i=sqrt(-1). - _Bruno Berselli_, Feb 25 2011
%F 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
%F a(n) * A060819(n+2) = A142705(n+1) = A061037(2n+2). - _Paul Curtz_, Mar 02 2011
%F a(n) = n - (n/2)*floor(((n-1) mod 4)/3). - _Gary Detlefs_, Apr 14 2013
%F a(2^n) = A090129(n+1). - _R. J. Mathar_, Oct 09 2014
%F a(n) = n*(7 - (-1)^n - 2*cos(n*Pi/2))/8. - _Federico Provvedi_, Jan 02 2018
%F E.g.f.: (1/4)*x*(4*cosh(x) + sin(x) + 3*sinh(x)). - _Stefano Spezia_, Jan 26 2020
%F Sum_{k=1..n} a(k) ~ (7/16) * n^2. - _Amiram Eldar_, Nov 28 2022
%p A186646 := proc(n) if n mod 4 = 0 then n/2 ; else n ; end if; end proc ;
%t 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 *)
%t Table[n (7 - (-1)^n - 2 Cos[n Pi/2])/8, {n, 100}] (* _Federico Provvedi_ , Jan 02 2018 *)
%o (PARI) a(n)=if(n%4,n,n/2) \\ _Charles R Greathouse IV_, Oct 16 2015
%o (Python)
%o def A186646(n): return n if n&3 else n>>1 # _Chai Wah Wu_, Jan 10 2023
%Y Cf. A000224 (size of the set of moduli of k^2 mod n), A019554, A060819, A061037, A090129, A142705, A164115, A283971.
%K nonn,easy,mult
%O 1,2
%A _R. J. Mathar_, Feb 25 2011
|
