Сколько существует натуральных чисел n, меньших 1000, для которых (2^n)-n делится на 7 ?

@GonzoPlay · Регистрация: 18.01.2021

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

@Fudthhh · 21.06.2021, 14:23

Python
1
print(sum((2**n - n) % 7 == 0 for n in range(1000)))

@Catstail · 22.06.2021, 05:02

Fudthhh, лобовое неэффективное решение...

@Gdez · 22.06.2021, 10:29

Python
1
2
3
4
5
k, cnt = 1, 0
for i in range(1,10000000):
    k = (k<<1)%7
    cnt += k-i%7 == 0
print(cnt)

@Arsegg · 22.06.2021, 16:28

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

лобовое неэффективное решение...

Python
1
print(142)

А такое?

@Catstail · 22.06.2021, 17:00

Arsegg, а это вообще не решение. Оно ничем не лучше вот такого (неправильного)

Python
1
print(777)

@Arsegg · 22.06.2021, 17:04

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

а это вообще не решение. Оно ничем не лучше вот такого (неправильного)

Ну их же конечное число.

@Catstail · 22.06.2021, 17:05

Поскольку верно равенство 7=2³-1, то 2ⁿ-n=7*^2n-3+2^n-3-n. Поэтому, остаток от деления (2ⁿ-n) на 7 равен остатку от деления на 7 величины (2^n-3-n). Далее: (2^n-3-n) = 7*2^n-6+2^n-6-n. Остаток от деления (2^n-3-n) на 7 равен остатку от деления на 7 величины (2^n-6-n). Таким образом, чтобы оценить остаток от деления (2ⁿ-n) на 7 нужно вычитать из показателя степени по тройке до тех пор, пока показатель не станет меньше 32 (когда степень можно вычислить явно).

Соображения, приведенные выше, позволяют решить эту задачу не только на Питоне (где можно расслабиться и применить прямой перебор), но и на любом ЯП.

@Gdez · 22.06.2021, 19:09

Без возведений в степень через диофантовы уравнения

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
32
33
34
35
36
37
38
39
40
41
42
43
from math import ceil
 
def gcd_extended(num1, num2):
    if num1 == 0:
        return (num2, 0, 1)
    else:
        div, x, y = gcd_extended(num2 % num1, num1)
    return (div, y - (num2 // num1) * x, x)
    
n = 1000 # int(input())
 
##########
# нахождение "первых" степеней,
# при которых (2^i) % 7 == i % 7
# (2^i) % 7 -> [1, 2, 4]
# весь код до следующих хешей
# легко вручную вычислить
a = 7
b = -3
c_rem = [6, 3, 2]
c_y = [6, 5, 3]
k = []
 
d, xt, yt = gcd_extended(7, -3)
 
i = 0
for c in c_rem:
    xo1 = xt * c
    yo1 = yt * c
    while xo1 + d*b > 0 and yo1 - d*a > 0:
        xo1 += d*b 
        yo1 -= d*a 
    k.append(a*xo1 - c_y[i])
    i += 1
print(k)
##########
##########
 
res = 0
lcm = abs(a*b) // d
for i in k:
    res += ceil((n - i + 1) / lcm)
print(res)

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@GonzoPlay -5 / 0 / 0 Регистрация: 18.01.2021 Сообщений: 21

	Сколько существует натуральных чисел n, меньших 1000, для которых (2^n)-n делится на 7 ? 21.06.2021, 13:55. Показов 5467. Ответов 8 Метки нет (Все метки) Сколько существует натуральных чисел n, меньших 1000, для которых (2^n)-n делится на 7 ? 0

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,734 Записей в блоге: 14
	22.06.2021, 05:02
	Fudthhh, лобовое неэффективное решение... 0

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,734 Записей в блоге: 14
	22.06.2021, 17:05
	Поскольку верно равенство 7=2³-1, то 2ⁿ-n=7^2n-3+2^n-3-n. Поэтому, остаток от деления (2ⁿ-n) на 7 равен остатку от деления на 7 величины (2^n-3-n). Далее: (2^n-3-n) = 72^n-6+2^n-6-n. Остаток от деления (2^n-3-n) на 7 равен остатку от деления на 7 величины (2^n-6-n). Таким образом, чтобы оценить остаток от деления (2ⁿ-n) на 7 нужно вычитать из показателя степени по тройке до тех пор, пока показатель не станет меньше 32 (когда степень можно вычислить явно). Соображения, приведенные выше, позволяют решить эту задачу не только на Питоне (где можно расслабиться и применить прямой перебор), но и на любом ЯП. 1