Teoria liczbTrudneZadanie nr 3720

Które liczby od 1 do 60 są sumami cyfr kwadratów liczb całkowitych dodatnich

Cechy podzielności Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Ile liczb ze zbioru \(\{1,2,\dots,60\}\) jest równych sumie cyfr (w zapisie dziesiętnym) kwadratu pewnej liczby całkowitej dodatniej?

+16 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Suma cyfr daje tę samą resztę z dzielenia przez \(9\) co sama liczba. Jakie reszty z dzielenia przez \(9\) dają kwadraty? Do konstrukcji użyj kwadratów liczb postaci \(10^m-c\) dla małych \(c\).

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Suma cyfr \(S(N)\) przystaje do \(N\) modulo \(9\), a kwadraty dają reszty \(0,1,4,7\) z dzielenia przez \(9\). Zatem \(S(n^2)\bmod 9\in\{0,1,4,7\}\).
  2. Dla \(m\ge1\): \((10^m-1)^2=(10^m-2)\cdot10^m+1\) ma sumę cyfr \(9(m-1)+8+1=9m\); \((10^m-2)^2=(10^m-4)\cdot10^m+4\) — sumę \(9(m-1)+6+4=9m+1\); \((10^m-3)^2=(10^m-6)\cdot10^m+9\) — sumę \(9(m-1)+4+9=9m+4\); \((10^m-5)^2=(10^{m-1}-1)\cdot10^{m+1}+25\) — sumę \(9(m-1)+7\).
  3. Razem z \(S(1)=1\) i \(S(4)=4\) dostajemy wszystkie liczby \(k\le60\) o resztach \(0,1,4,7\) modulo \(9\): \(9,18,\dots,54\) (\(6\) liczb), \(1,10,\dots,55\) (\(7\)), \(4,13,\dots,58\) (\(7\)), \(7,16,\dots,52\) (\(6\)).
  4. Odpowiedź: \(26\).

Odpowiedź: \(26\)

Czego warto się nauczyć?

Teoria liczb to podzielność, reszty i cykle potęg — dział, w którym krótki pomysł zastępuje długi rachunek.

Więcej zadań z teorii liczb →

Podobne zadania