Число троек (a,b,c), для которых f(a,b,c)=n

[nnosipov]

Написать программу, которая для данного натурального $n$ находит количество троек $(a,b,c)$ целых неотрицательных чисел таких, что $(3a+2b+c)^2+18a+8b+2c+1=n$. (Число $n$ предполагается достаточно большим, чтобы исключить прямой перебор. Наверное, подойдут числа $n \approx 10^9$.)

[zykov]

Обозначим $p=3a+2b+c$ и $q=3a+b$.
Тогда $(3a+2b+c)^2+18a+8b+2c+1=p^2+2p+4q+1=(p+1)^2+4q$.
При этом $p-q=b+c \geq 0$, т.е. $p \geq q$.

Для данного $n$ будет $(p+1)^2=n-4q$.
Если $n$ при делении на 4 даёт остаток 2 или 3, то решений нет.
При остатке 0 кандидаты в $p$ - нечётные, при остатке 1 кандидаты в $p$ - чётные, в диапазоне $\sqrt{n+8}-3 \leq p \leq \sqrt n - 1$.
Получаем набор пар $(p,q)$, так что $q=\frac{n-(p+1)^2}{4}$.
Для каждой пары $(p,q)$ будет набор пар $(b,c)$, таких что $b+c=p-q$.
Но $3a=q-b$, т.е. из этих пар берем только $b\leq \min(q,p-q)$ и $q-b$ делится на 3.
Т.е. берем все такие $b$, тогда $a=\frac{q-b}{3}$ и $c=p-q-b$.

Можно заметить, что $(\sqrt n - 1)-(\sqrt{n+8}-3)$ возрастает и в пределе стремится к 2, так что для каждого $n$ будет не более одного кандидата $p$.

-- 23.09.2021, 22:45 --

Если интересно, вот Matlab код:

Используется синтаксис Matlab M

function r = count_abc(n)
  n4 = mod(n,4);
  r = 0;
  if n4==2 || n4==3; return; endif;
  n1 = ceil(sqrt(n+8)-3);
  n2 = floor(sqrt(n)-1);
  if n2<n1 || (n2==n1 && mod(n1+n4,2)==0); return; endif;
  p = n1;
  if mod(p+n4,2)==0; p = p+1; endif;
  q = (n-(p+1)^2)/4;
  b1 = min(q,p-q)-mod(q,3);
  r = floor(b1/3)+1;
endfunction

-- 23.09.2021, 22:47 --

Пример:

Используется синтаксис Matlab M

>> count_abc(1000000000)
ans =  4094
>> count_abc(1000000001)
ans =  1177

[nnosipov]

Да, все верно.

[zykov]

Спасибо! Было интересно.