Отправлено: 20.12.23 23:07. Заголовок: Задача 16 - №6565

Обозначим частное от деления натурального числа a на натуральное число b как a // b, а остаток как a%b. Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n // 3 + n % 3, если n < 9;
F(n) = F(n // 9) + F(n % 9), если n ≥ 9.
Определите количество значений n < 9^9, для которых функция F(n) = 33.
При решении количество операций будет слишком огромным, ответа придётся ждать очень долго, и вряд ли ты его вообще дождёшься.
Есть ли вообще способ решить эту задачу быстро с помощью кода ?

ВОТ РЕШЕНИЕ(НЕРАБОЧЕЕ):
def F(n, cache):
if n < 9:
return n // 3 + n % 3
else:
if n not in cache:
cache[n] = F(n // 9, cache) + F(n % 9, cache)
return cache[n]

count = 0
cache = {}
for n in range(1, 9**9):
if F(n, cache) == 33:
count += 1

print(count)

 Отправлено: 30.12.23 14:54. Заголовок: Вообще задача сводит..

Вообще задача сводится к нахождению чисел, сумма цифр в троичной записи которых равна 33
Вот код, который считает мгновенно.

 
 k=[0]*34 
 k[0]=k[1]=k[2]=1 
 for c in range(17): 
     k=[k[0],k[1]+k[0]]+[sum(k[i - 2:i + 1]) for i in range(2,34)] 
 print(k[-1]) 
 

Вот несколько кодов, которые решают задачу обычным способом, но все они считают от 12 до 16 минут

 
 from time import * 
 setrecursionlimit(2**15) 
 kol=0 
 @lru_cache(2**20) 
 def F(n): 
     if n < 9: return n // 3 + n % 3 
     return F(n // 9) + F(n % 9) 
 for c in range(9**9): 
     if F(c)==33: 
         kol+=1 
         print(kol,c) 
 

 
 from functools import * 
 kol=0 
 tr=lru_cache(2**20)(lambda n: tr(n//3)+n%3 if n>0 else 0) 
 for c in range(int('2'*16,3), 9**9):  kol+=tr(c)==33 
 print(kol) 
 

 
 setrecursionlimit(2**15) 
 f=lru_cache(2**20)(lambda n,s: f(n,s+'0')+f(n+1,s+'1')+f(n+2,s+'2') if n<33 and len(s)<18 else n==33 and int(s,3)<=9**9) 
 print(f(0,'')) 
 

 Отправлено: 04.02.24 21:37. Заголовок: 16-6565 Аналитическое решение

Мои соображения следующие. Так как F(9*k0+p0) = F(k0)+F(p0), а p0 можно рассматривать как последнюю цифру числа 9*k0+p0, записанного в девятеричной системе счисления, то применяя тот же подход для F(k0) получим F(9*k0+p0) = F(9*k1+p1) + F(p0) = F(k1) + F(p1) + F(p0) и т. д.
Следовательно, итог есть сумма F(p) для каждой цифры в девятеричном представлении числа. Легко получить значение F(p) для каждой цифры. Соберём их в список V=[0,1,2,1,2,3,2,3,4], тогда F(p) = V[p]. Получить сумму 33 можно следующими способами:
1) 8*4 + 1 (отсюда следует, что в исходном числе должно быть 9 цифр, 8 даст максимум 32). Значит в числе должно быть 8 восьмерок и одна цифра 1 или 3 на любом оставшемся месте. Это 18 вариантов.
2) 7*4+3+2. Значит в числе должно быть 7 восьмерок, одна цифра 5 или 7 и одна цифра 2, 4 или 6 на двух оставшихся местах. Комбинируя эти цифры получим 12 пар, а всего C(2,9)*12 = 432 варианта.
3) 6*4+3*3. Значит в числе должно быть 6 восьмерок, остальные три места занимают цифры 5 и 7, они дают 8 вариантов, всего C(3,9)*8 = 672 варианта.
Складывая эти значения получим ответ: 1122

 Отправлено: 04.02.24 22:03. Заголовок: 16-6565 Аналитическое решение

Мои соображения следующие. Так как F(9*k0+p0) = F(k0)+F(p0), а p0 можно рассматривать как последнюю цифру числа 9*k0+p0, записанного в девятеричной системе счисления, то применяя тот же подход для F(k0) получим F(9*k0+p0) = F(9*k1+p1) + F(p0) = F(k1) + F(p1) + F(p0) и т. д.
Следовательно, итог есть сумма F(p) для каждой цифры в девятеричном представлении числа. Легко получить значение F(p) для каждой цифры. Соберём их в список V=[0,1,2,1,2,3,2,3,4], тогда F(p) = V[p]. Получить сумму 33 можно следующими способами:
1) 8*4 + 1 (отсюда следует, что в исходном числе должно быть 9 цифр, 8 даст максимум 32). Значит в числе должно быть 8 восьмерок и одна цифра 1 или 3 на любом оставшемся месте. Это 18 вариантов.
2) 7*4+3+2. Значит в числе должно быть 7 восьмерок, одна цифра 5 или 7 и одна цифра 2, 4 или 6 на двух оставшихся местах. Комбинируя эти цифры получим 12 пар, а всего C(2,9)*12 = 432 варианта.
3) 6*4+3*3. Значит в числе должно быть 6 восьмерок, остальные три места занимают цифры 5 и 7, они дают 8 вариантов, всего C(3,9)*8 = 672 варианта.
Складывая эти значения получим ответ: 1122