Search

Let l ( n ) l(n) denote, as usual, the length of a shortest addition chain for a given positive integer n. The most famous unsolved problem in addition chains is Scholz’s 1937 conjecture that for all natural numbers n , l ( 2 n − 1 ) ≤ l ( n ) + n − 1 n,l({2^n} - 1) \leq l(n) + n - 1 . While this conjecture has been proved for certain classes of values of n, its validity for all n is yet an open problem. In this paper, we put forth a new conjecture, namely, that for each integer n ≥ 1 n \geq 1 there exists an addition chain for 2 n − 1 {2^n} - 1 whose length equals l ( n ) + n − 1 l(n) + n - 1 . Obviously, our conjecture implies (and is stronger than) Scholtz’s conjecture. However, it is not as bold as conjecturing that l ( 2 n − 1 ) = l ( n ) + n − 1 l({2^n} - 1) = l(n) + n - 1 , which is known to hold, so far, for only the twenty-one values of n which were obtained by Knuth and Thurber after extensive computations. By utilizing a series of algorithms we establish our conjecture for all n ≤ 128 n \leq 128 by actually computing the desired addition chains. We also show that our conjecture holds for infinitely many n, for example, for all n which are powers of 2.

Let Q k ( n ) {Q_k}(n) be the number of k-free integers ⩽ n \leqslant n and d ( Q k ) d({Q_k}) the Schnirelmann density of the k-free integers. If k ⩾ 5 k \geqslant 5 , it is shown that Q k ( n ) / n = d ( Q k ) {Q_k}(n)/n = d({Q_k}) for some n satisfying 6 k / 2 ⩽ n > 6 k {6^k}/2 \leqslant n > {6^k} and certain other properties, and that \[ d ( Q k ) ⩾ 1 − 2 − k − 3 − k − 5 − k + ( 3 − k + 2 ⋅ 5 − k ) ( 6 k − 3 k + 1 ) − 1 . d({Q_k}) \geqslant 1 - {2^{ - k}} - {3^{ - k}} - {5^{ - k}} + ({3^{ - k}} + 2 \cdot {5^{ - k}}){({6^k} - {3^k} + 1)^{ - 1}}. \] d ( Q k ) d({Q_k}) and the n for which Q k ( n ) / n = d ( Q k ) {Q_k}(n)/n = d({Q_k}) are found for 7 ⩽ k ⩽ 12 7 \leqslant k \leqslant 12 .

Let k be a fixed integer ⩾ 1 \geqslant 1 and define τ k ( n ) = Σ d k / n 1 {\tau _k}(n) = {\Sigma _{{d^k}/n}}1 . Thus τ 1 ( n ) {\tau _{1}}(n) is the ordinary divisor function and τ k ( n ) {\tau _k}(n) is the number of kth powers dividing n. We derive the asymptotic behaviour as n → ∞ n \to \infty of P k ( n ) {P_k}(n) defined by \[ ∑ n = 0 ∞ P k ( n ) x n = ∏ n = 1 ∞ ( 1 − x n ) − τ k ( n ) . \sum \limits _{n = 0}^\infty {{P_k}(n){x^n} = \prod \limits _{n = 1}^\infty {{{(1 - {x^n})}^{ - {\tau _k}(n)}}} .} \] Thus P k ( n ) {P_k}(n) is the number of partitions of n where we recognize τ k ( m ) {\tau _k}(m) different colours of the integer m when it occurs as a summand in a partition. The case k = 2 k = 2 is of special interest since the number f ( n ) f(n) of semisimple rings with n elements when n = q 1 l 1 q 2 l 2 … n = q_1^{{l_1}}q_2^{{l_2}} \ldots is given by f ( n ) = P 2 ( l 1 ) P 2 ( l 2 ) … f(n) = {P_2}({l_1}){P_2}({l_2}) \ldots .

In 1929, in the course of proving certain results stated by Ramanujan concerning his continued fraction, G. N. Watson proved an identity involving five infinite products and an infinite series. In 1938, Watson proved another identity which again involved five products. Finally in 1961, one more quintuple product identity was established, this time by Basil Gordon. We show here that all these identities are equivalent. Also, with the help of the quintuple product identity and Jacobi’s triple product identity, we establish two new identities involving only series.

This paper generalizes and extends the recent results of George Andrews on Euler pairs. If S 1 {S_1} and S 2 {S_2} are nonempty sets of natural numbers, we define ( S 1 , S 2 ) ({S_1},{S_2}) to be an Euler pair of order r r whenever q r ( S 1 ; n ) = p ( S 2 ; n ) {q_r}({S_1};n) = p({S_2};n) for all natural numbers n n , where q r ( S 1 ; n ) {q_r}({S_1};n) denotes the number of partitions of n n into parts taken from S 1 {S_1} , no part repeated more than r − 1 r - 1 times ( r > 1 ) (r > 1) , and p ( S 2 ; n ) p({S_2};n) the number of partitions of n n into parts taken from S 2 {S_2} . Using a method different from Andrews’, we characterize all such pairs, and consider various applications as well as an extension to vector partitions.

We characterize all multiplicative arithmetical functions f k ( r ) {f_k}(r) such that an identity of the form \[ ∑ r = 1 ∞ f k ( r ) c k ( n , r ) = q k ( n ) g ( k ) , g ( k ) ≠ 0 , \sum \limits _{r = 1}^\infty {{f_k}(r){c_k}(n,r) = {q_k}(n)g(k),\quad g(k) \ne 0,} \] holds for all n, where q k ( n ) {q_k}(n) is the characteristic function of the set of k-free integers and c k ( n , r ) {c_k}(n,r) is the generalized Ramanujan sum. This characterization yields several arithmetical identities of the above form including an identity of Eckford Cohen, which occurs as a special case of our theorem on taking f k ( r ) = μ ( r ) / J k ( r ) {f_k}(r) = \mu (r)/{J_k}(r) and g ( k ) = ζ ( k ) g(k) = \zeta (k) .

Two theorems are given about partitions in which the multiplicity of the parts satisfies certain conditions. One of these theorems generalizes a recent result of Andrews concerning partitions in which a part with an odd multiplicity occurs at least 2 r + 1 2r + 1 times.