login
Sum of all partial fractions in the algorithm used for calculation of A002326(n).
10

%I #38 Oct 07 2017 21:54:23

%S 1,1,4,1,13,25,36,1,38,81,12,26,124,121,196,1,103,73,324,42,224,175,

%T 91,147,232,14,676,170,303,841,900,1,264,1089,385,364,93,301,585,563,

%U 1093,1681,44,355,152,118,83,484,1254,763,2500,1043,156,2809,996,564,952,931,71,387,3325,176,3124,1,649,4225,554,1081

%N Sum of all partial fractions in the algorithm used for calculation of A002326(n).

%C This sequence gives important additional insight into the algorithm for the calculation of A002326 (see A179680 for its description). Let us estimate how many steps are required before (the first) 1 will appear. Note that all partial fractions (which are indeed, integers) are odd residues modulo 2*n+1 from the interval [1,2*n-1]. So, if there is no a repetition, then the number of steps does not exceed n. Suppose then that there is a repetition before the appearance of 1. Then for an odd residue k from [1, 2*n-1], 2^m_1 == 2^m_2 == k (mod 2*n+1) such that m_2 > m_1. But then 2^(m_2-m_1) == 1 (mod 2*n+1). So, since m_2 - m_1 < m_2, it means that 1 should appear earlier than the repetition of k, which is a contradiction. So the number of steps <= n. For example, for n=9, 2*n+1 = 19, we have exactly 9 steps with all other odd residues <= 17 modulo 19 appearing before the final 1: 5, 3, 11, 15, 17, 9, 7, 13, 1.

%C A001122 gives the odd numbers k such that a((k-1)/2) = A000290((k-1)/2).

%H Antti Karttunen, <a href="/A292270/b292270.txt">Table of n, a(n) for n = 0..10001</a>

%F For all n >= 1, A000196(a((A001122(1+n)-1)/2)) = (A001122(1+n)-1)/2, in other words, a(A163782(n)) = A000290(A163782(n)).

%e Let n = 9. According to the comment, a(9) = 5 + 3 + 11 + 15 + 17 + 9 + 7 + 13 + 1 = 81.

%o (PARI)

%o A000265(n) = (n >> valuation(n, 2));

%o A006519(n) = 2^valuation(n, 2);

%o A292270(n) = { my(x = n+n+1, z = ((1+x)/A006519(1+x)), m = A000265(1+x)); while(m!=1, z += ((x+m)/A006519(x+m)); m = A000265(x+m)); z; };

%o (Scheme) (define (A292270 n) (let ((x (+ n n 1))) (let loop ((z (/ (+ 1 x) (A006519 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (+ z (/ (+ x m) (A006519 (+ x m)))) m))))))

%Y Cf. A000265, A000290, A001122, A001917, A002326, A006519, A163782, A179382, A179680, A292239, A292265, A292947, A293218, A293219.

%Y Cf. A000225 (gives the positions of ones), A292938 (of squares), A292939 (and the corresponding odd numbers), A292940 (odd numbers corresponding to squares larger than one), A292379 (odd numbers corresponding to squares less than n^2).

%K nonn

%O 0,3

%A _Vladimir Shevelev_ and _Antti Karttunen_, Oct 05 2017