cp's OEIS Frontend

A260965 Smallest number r>=3 such that for k>=r the number k - 3 + prime(n) can be represented in the form x_1*...*x_k + x_1 + ... + x_k, where 1 <= x_1 <= ... <= x_k, or a(n)=0 if there is no such r.

%I A260965 #80 Nov 15 2024 06:57:58
%S A260965 0,0,0,0,0,0,0,3,4,3,0,0,4,0,3,0,3,3,0,4,3,3,4,3,4,0,3,5,3,4,3,3,3,3,
%T A260965 3,3,4,3,4,3,3,0,0,5,3,3,3,0,3,3,4,3,3,0,3,3,3,3,3,3,4,3,3,3,3,4,3,3,
%U A260965 4,3,3,3,3,0,3,3,3,3,3,3,3,0,5,3,3,3,3,3,3,3,3,3,4,3,3,3,3,4,3,3,3,3,4,3,3,4,3,3,3
%N A260965 Smallest number r>=3 such that for k>=r the number k - 3 + prime(n) can be represented in the form x_1*...*x_k + x_1 + ... + x_k, where 1 <= x_1 <= ... <= x_k, or a(n)=0 if there is no such r.
%C A260965 Let m>=k-1. The condition 'm - k + 3 is prime' is a necessary condition for the non-representation of m by the form A = x_1*...*x_k + x_1 + ... + x_k, where 1 <= x_1 <= ... <= x_k (see link [Shevelev], Proposition 2). In particular, if m - k + 3 = prime(n), then a sufficient condition for that is a(n) = 0 or a(n) > k.
%C A260965 Conjecture. The sequence contains only a finite number of zero terms.
%C A260965 About the conjecture, for n <= 10000, 23 values a(n) are 0, of which 19 have n <= 100. The highest such n is 450. a(n) is at most five for n <= 10000 and mostly 3 (9747 times). - _David A. Corneth_, Aug 16 2015
%C A260965 Upper estimate of a(n). A representation of prime(n) + k - 3 for the minimal possible k by the form A we call optimal. Show that in an optimal representation all x_i>=2.
%C A260965 Indeed, let x_1 = ... = x_u = 1 and x_i >= 2 for u+1 <= i <= k, such that prime(n) + k - 3 = x_(u+1)*...*x_k + u + x_(u+1) + ... + x_k be an optimal representation (note that u<k, otherwise A = k+1 which is not k-3 + prime). Set k_1 = k - u; y_j = x_(u+j). Then prime(n) + k_1 - 3 = y_1*...*y_(k_1) + y_1 + ... + y_(k_1). But k_1 < k, which contradicts the optimality of A. QED
%C A260965 So for an optimal representation, prime(n) + k - 3 = A >= 2^k + 2*k and 2^k + k + 3 <= prime(n). Thus a(n) = k_min < log_2(prime(n)) (cf. formula).
%C A260965 a(n)>0 iff either there exists t_2>=1 such that B(t_2) = 2^t_2 + t_2 + 3 = prime(n) or there exist t_2>=0, t_3>=1 such that B(t_2, t_3) = 2^t_2*3^t_3 + t_2 + 2*t_3 + 3 = prime(n) or there exist t_2>=0, t_3>=0, t_4>=1 such that B(t_2, t_3, t_4) = 2^t_2*3^t_3*4^t_4 + t_2 + 2*t_3 + 3*t_4 + 3 = prime(n), etc.
%C A260965 For a proof, distinguish the following cases for x_i >= 2, i=1,...,k, and A = x_1*...*x_k + x_1 + ... + x_k:
%C A260965 (i) all x_i = 2. Here k=t_2 and A = A(t_2) = 2^t_2 + 2*t_2. If this is t_2 - 3 + prime, then prime = 2^t_2+t_2+3 = B(t_2). For example, for t_2=4 we have 23 = prime(9). Thus for k>=4, k - 3 + prime(9) is represented by a considered form A and a(9)=4.
%C A260965 (ii) the first t_2 consecutive x_i = 2 and t_3 consecutive x_i = 3. Note that t_3 >= 1 (otherwise, we have case (i)). Here A = A(t_2, t_3) = (2^t_2)*(3^t_3) + 2*t_2 + 3*t_3. If this is k - 3 + prime(n) = t_2 + t_3 -3 + prime(n), then prime(n) = (2^t_2)*(3^t_3) + t_2 + 2*t_3 + 3 = B(t_2, t_3). For example, for t_2=2, t_3=1 we have 19=prime(8). Thus for k>=2+1=3, k-3+prime(8) is represented by a considered form A and a(8)=2+1=3.
%C A260965 etc. QED
%C A260965 For an algorithm of calculation of a(n), see link [Shevelev], pp. 4-5.
%H A260965 David A. Corneth, <a href="/A260965/b260965.txt">Table of n, a(n) for n = 1..10000</a>
%H A260965 David A. Corneth, <a href="/A260965/a260965_1.gp.txt">The tuples of (x_1,...,x_k) that give a(n)</a>
%H A260965 Vladimir Shevelev, <a href="http://arxiv.org/abs/1508.03970">Representation of positive integers by the form x1...xk+x1+...+xk</a>, arXiv:1508.03970 [math.NT], 2015.
%F A260965 a(n) <= floor(log_2(prime(n))).
%e A260965 a(8)=3. Indeed, prime(8) = 19 and for k=3, set x_1 = x_2 = 2, x_3 = 3, and, for k>=4, set x_1 = ... = x_(k-3) = 1, x_(k-2) = x_(k-1) = 2, x_k = 3.
%e A260965 In both cases, x_1*...*x_k + x_1 + ... + x_k = 2*2*3 + (k-3) + 2 + 2 + 3 = k + 19 - 3.
%Y A260965 Cf. A260803, A260804.
%K A260965 nonn
%O A260965 1,8
%A A260965 _Vladimir Shevelev_, Aug 06 2015
%E A260965 More terms from _David A. Corneth_, Aug 16 2015