Sum трех квадратов натуральных чисел

@Glbvnts · Регистрация: 10.03.2020

Студворк — интернет-сервис помощи студентам

Ввести произвольную последовательность натуральных чисел. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов натуральных чисел.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
seq = set(eval(input()))
count = 0
for n in seq:
    x = 1
    while x * x <= n:
        y = x
        while y * y <= n:
            z = y
            while z * z <= n:
                if n == x * x + y * y + z * z:
                    count += 1
                z += 1
            y += 1
        x += 1
print(count)

Не работает на таком тесте: range(100,500,3). Ответ должен быть 101, а у меня 186. Никак не соображу в чем ошибка, подскажите пожалуйста.

@Gdez · 14.11.2021, 02:20

Glbvnts, потому что (запусти код):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
seq = list(range(100,500,3))
count = 0
res = []
for n in seq:
    x = 1
    while x * x <= n:
        y = x
        while y * y <= n:
        # while y * y <= n - x * x:
            z = y
            while z * z <= n:
            # while z * z <= n - x * x - y * y:
                if n == x * x + y * y + z * z:
                    
                    ########
                    res.append(x*x + y*y + z*z)
                    ########
                    
                    count += 1
                z += 1
            y += 1
        x += 1
print(count)
 
########
for elem in sorted(res):
    print(elem)
print(len(set(res)))
########

И счетчики в циклах можно было бы уменьшить (9 и 12 строки)

Добавлено через 4 минуты
Оптимальнее можно так :

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def squares_sum(num):
 
    d1 = int(num**.5)
    for i1 in range(d1, 0, -1):
        if i1**2 == num:
            continue
 
        num1 = num - i1**2
        d2 = int(num1**.5)
 
        for i2 in range(d2, 0, -1):
            if i2**2 == num1:
                continue
 
            num2 = num1 - i2**2
            d3 = int(num2**.5)
 
            for i3 in range(d3, 0, -1):
                if i3**2 == num2:
                    return True
 
    return False
 
 
print(sum(1 for i in range(100, 500, 3) if squares_sum(i))

@Glbvnts · 14.11.2021, 02:41 **[ТС]**

Смысл этих строк понятен.

Сообщение от Gdez

# while y * y <= n - x * x:

Сообщение от Gdez

# while z * z <= n - x * x - y * y:

Я правильно понял, что set здесь для того, что бы исключить повторяющиеся элементы в res?

Сообщение от Gdez

print(len(set(res)))

Если так, то как так получилось, что я наборы повторяющиеся по типу (1, 1, 2; 1, 2, 1; 2, 1, 1) подсчитал несколько раз, ведь рассматриваемые наборы не убывающие или дело не в этом?

@Gdez · 14.11.2021, 07:14

Glbvnts, повторяющиеся суммы квадратов элементов, а не элементы x, y, z

Добавлено через 6 минут
И в крайнем коде мне нужно было без третьего цикла

(в свое время писалось для четырех, не трех, квадратов):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def squares_sum(num):
 
    d1 = int(num**.5)
    for i1 in range(d1, 0, -1):
        if i1**2 == num:
            continue
 
        num1 = num - i1**2
        d2 = int(num1**.5)
 
        for i2 in range(d2, 0, -1):
            if i2**2 == num1:
                continue
 
            num2 = num1 - i2**2
            d3 = int(num2**.5)
            if d3*d3 == num2:
                return True
 
 
    return False
 
 
print(sum(1 for i in range(100, 500, 3) if squares_sum(i)))

@Glbvnts · 14.11.2021, 13:57 **[ТС]**

Сообщение от Gdez

без третьего цикла

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
seq = set(eval(input()))
res = []
for n in seq:
    x = 1
    while x * x <= n/3:
        n_x = n - x*x
        y = x
        while y * y <= n_x/2:
            n_xy = n_x - y*y
            z = int(n_xy ** 0.5)
            while z * z <= n_xy:
                if n_xy == z * z:
                    res.append(x * x + y * y + z * z)
                z += 1
            y += 1
        x += 1
 
print(len(set(res)))

Здесь можно избавиться от цикла для z, но тогда тайм аут на тестах:
range(100, 500, 3),
__import__("itertools").chain(range(1,10 050,101),range(7000,9900,117)).
Если оставить с этим циклом, то превышения времени не будет)))), но как и Ваша программа к сожалению тоже выдает тайм аут на каком то тесте размер файла которого 99999

@Gdez · 14.11.2021, 20:54

Glbvnts, попробуй

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def squares_sum(num):
    def check(num):
        while num%4 == 0:
            num //= 4
        return (num - 7) % 8 != 0
        
    if check(num):
        d1 = int(num**.5)
        t1 = int((num/3)**.5)
 
        for i1 in range(d1, t1, -1):
            if i1*i1 != num:
                num1 = num - i1*i1
                d2 = int(num1**.5)
                t2 = int((num1/2)**.5)
                t2 -= (t2!=0)
 
                for i2 in range(d2, t2, -1):
                    if i2*i2 != num1:
                        num2 = num1 - i2*i2
                        d3 = int(num2**.5)
                        if d3*d3 == num2:
                            return True
    return False
 
 
c = 0
for i in range(1, 300000):
    if squares_sum(i) :
        c += 1
print(c)

@eaa · 15.11.2021, 13:18

Python
1
2
3
4
5
6
7
8
9
10
11
from random import randint
def is_three(n):  # по теореме Лежандра о трёх квадратах
    while n % 4 == 0:
        n /= 4
    return n % 8 != 7
 
 
n = 100
a = [randint(1, 10000) for _ in range(n)]
print(a)
print(len(filter(is_three, set(a))))

Наилучшее представление числа суммой квадратов

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .