Всем привет и три задачи.
Первая вроде известная, остальные вроде мои

1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?

2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?

3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?

PS1
Суммы везде начинаются не обязательно с 1.

PS2 (для программистов на си )
0 — НЕ натуральное число

Здравствуйте, Pushkin, Вы писали:

P>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?
Для первых 1023 их 55 (число способов выбрать диапазон в 10ти битах), однако некоторые нам не подходят, ибо больше 1000. Очевидно, что они имеют все старшие биты установленными, и максимум 4 нулевых бита. Итого, таких чисел ровно 4. Ответ: 51
Так?

Здравствуйте, Pushkin, Вы писали:

P>3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?
1000 само число в степени 1

Здравствуйте, orangy, Вы писали:

P>>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?
O>Для первых 1023 их 55 (число способов выбрать диапазон в 10ти битах), однако некоторые нам не подходят, ибо больше 1000. Очевидно, что они имеют все старшие биты установленными, и максимум 4 нулевых бита. Итого, таких чисел ровно 4. Ответ: 51
O>Так?

У меня чой-то другой ответ
Но может я и не прав, подождём ещё мнений

Здравствуйте, orangy, Вы писали:

O>Здравствуйте, Pushkin, Вы писали:

P>>3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?
O>1000 само число в степени 1

Надо, чтобы в разложении было несколько членов (>1).
А то так и первое разложение тоже для любого числа получишь.

Здравствуйте, Pushkin, Вы писали:

Комбинируем
P>1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?
с
P>3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?
и получаем:
4) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы одинаковых натуральных степеней последовательных натуральных чисел. Например, 1^3 + 2^3 + 3^3 = 36.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, orangy, Вы писали:

P>>>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?
O>>Для первых 1023 их 55 (число способов выбрать диапазон в 10ти битах), однако некоторые нам не подходят, ибо больше 1000. Очевидно, что они имеют все старшие биты установленными, и максимум 4 нулевых бита. Итого, таких чисел ровно 4. Ответ: 51
O>>Так?

P>У меня чой-то другой ответ
P>Но может я и не прав, подождём ещё мнений
Ну если несколько означает >1, то конечно другой ответ. А именно — 32.

Здравствуйте, Pushkin, Вы писали:

P>Надо, чтобы в разложении было несколько членов (>1).
P>А то так и первое разложение тоже для любого числа получишь.
Тогда уточняй еще, последовательных нескольких натуральных степеней или целых неотрицательных?

Здравствуйте, orangy, Вы писали:

P>>Надо, чтобы в разложении было несколько членов (>1).
P>>А то так и первое разложение тоже для любого числа получишь.
O>Тогда уточняй еще, последовательных нескольких натуральных степеней или целых неотрицательных?

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

Здравствуйте, orangy, Вы писали:

O>>>Для первых 1023 их 55 (число способов выбрать диапазон в 10ти битах), однако некоторые нам не подходят, ибо больше 1000. Очевидно, что они имеют все старшие биты установленными, и максимум 4 нулевых бита. Итого, таких чисел ровно 4. Ответ: 51
O>Ну если несколько означает >1, то конечно другой ответ. А именно — 32.

Вроде все верно, да не совсем. Число способов выбрать диапазон в 10 битах (если несколько означает >1) это число сочетаний из 10 по 2 (начало и конец диапазона), т.е. 45. А чисел с установленными старшими битами, которые больше 1000 не 4, а 5 (Вы забыли число 1023 в котором вообще нет нулевых битов).
Так что по моим прикидкам выходит 40.

Здравствуйте, Pushkin, Вы писали:

P>Всем привет и три задачи.
P>Первая вроде известная, остальные вроде мои

P>1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?

пусть первое число = k, длина серии = n
x = k*n + (0+1+...+(n-1)) = k*n + n*(n-1)/2

n=2. Покрывает все нечетные числа (x=2a+1 = a+(a+1)), начиная с 3.
n=3. Все числа, делящиеся на 3, начиная с 6.
И так далее.
Остаются не представленными только простые числа. А также число 1. (Сколько именно — не помню).

P>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?

x = 2^a + 2^(a+1) + ... + 2^(a+n-1) = 2^a * (2^n — 1)

Очевидно, каждая пара (a,n) дает уникальное число, x(a,n)==x(a',n') <=> a==a' & n==n'.

1000 = 1111101000_b

a(n=2) = 0..8
a(n=3) = 0..7
a(n=4) = 0..6
a(n=5) = 0..5
a(n=6) = 0..3 -- 1111110000_b больше, чем 1000
a(n=7) = 0..2
a(n=8) = 0..1
a(n=9) = 0

итого 1+2+3+4 + 6+7+8+9 = 40 чисел.

P>3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?

x = d^a * (1 + d^2 + ... + d^(n-1)) = d^a * (d^n-1) / (d-1)

x(a=0,n=2) = d^0 + d^1 = d+1

Откуда имеем: любое число, кроме 1, может быть представлено

Здравствуйте, kfmn, Вы писали:

K>Так что по моим прикидкам выходит 40.

О! Это мой размерчик

Здравствуйте, Pushkin, Вы писали:

P>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?
0..01 * 10
0..11 * 9
....
1..11 * 1

1+2+..10 = 55;

1111101000 — тысяча

отсеиваются
1111110000
1111111000
1111111100
1111111110
1111111111

Итого: 50

Здравствуйте, Кодт, Вы писали:

P>>1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?

К>пусть первое число = k, длина серии = n
К>x = k*n + (0+1+...+(n-1)) = k*n + n*(n-1)/2

К>n=2. Покрывает все нечетные числа (x=2a+1 = a+(a+1)), начиная с 3.
К>n=3. Все числа, делящиеся на 3, начиная с 6.
К>И так далее.
К>Остаются не представленными только простые числа. А также число 1. (Сколько именно — не помню).

7 — простое число
7=3+4


P>>2) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней двойки?

К>x = 2^a + 2^(a+1) + ... + 2^(a+n-1) = 2^a * (2^n — 1)
К>Очевидно, каждая пара (a,n) дает уникальное число, x(a,n)==x(a',n') <=> a==a' & n==n'.
К>итого 1+2+3+4 + 6+7+8+9 = 40 чисел.

Ок, этот ответ мне вполне нравится.

P>>3) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных степеней какого либо натурального числа?

К>x(a=0,n=2) = d^0 + d^1 = d+1
К>Откуда имеем: любое число, кроме 1, может быть представлено

Да, последняя задача, это просто шутка была
Есть несколько очевидных разложений для любого числа, отличного от 1

N = (N-1)^0+(N-1)^1
N = 1^1+1^2+...+1^N

Для 1 тоже можно, но бесконечной серией

1 = 2^(-1)+2^(-2)+2^(-3)+...

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Кодт, Вы писали:

P>>>1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?

P>7 — простое число
P>7=3+4
P>

Да. Это я погнал Будем думать дальше.

P>Для 1 тоже можно, но бесконечной серией

P>1 = 2^(-1)+2^(-2)+2^(-3)+...

Ну жульничать-то не будем, да? А если показатель взять нецелым (ведь о нем ничего не сказано)?
Тогда и степенями двойки можно что угодно представить.
x = (1+2)*2^(log2(x)-log2(3))

Здравствуйте, Кодт, Вы писали:

P>>>>1) Сколько среди первой тысячи натуральных чисел таких, которые могут быть представлены в виде суммы нескольких последовательных натуральных чисел?

К>Да. Это я погнал Будем думать дальше.

Итак, пусть x = k + (k+1) + ... + (k+n-1) == k*n + n*(n-1)/2

Для различных значений n мы получаем

x = 2k + 1
x = 3k + 3 = 3k' (по модулю 3)
x = 4k + 6 = 4k'+2 (по модулю 4)
...

нетрудно показать что получаются числа вида
x = (2m+1)k'
x = (2m)k' + m = m(2k'+1)

причем x >= x(k=1) = n + n(n-1)/2; n = {2m, 2m+1}

---

Очевидно, что x — это кратные нечетных чисел (2m+1 | 2k'+1). Вопрос: какие такие числа не являются кратными нечетным? Вспомним разложение на простые сомножители.
z = 2^i2 * 3^i3 * 5^i3 *...
То есть у любого числа, кроме чистой степени 2, есть нечетный делитель.

Итак. Стало ясно, что z=2^i невозможно представить суммой нескольких последовательных натуральных чисел. Таких чисел в 1..1000 всего 9: 2^0==1 .. 2^9==512.

---

Бывают ли еще варианты? Ведь у нас есть граничное условие для x(k,n) >= x(k=1;n)

Все нечетные, кроме 1, отсеяны. Будем искать среди четных. Но, как мы помним, хоть какому-то нечетному числу они кратны.

z = 3t --> z = (t-1)+t+(t+1)
z = 5t --> z = (t-2)+...+(t+2)
и т.п.
z = (2m+1)t --> z = (t-m)+...+(t+m)

Покрываются числа вида z=n*t, t > n/2
Что остается?

n=3 t>1 z>3
n=5 t>2 z>10. невозможно представить 10
n=7 t>3 z>21. невозможно представить 14
n=9 пропускаем, т.к. это кратные 3
n=11 t>5. невозможно представить 22, 44
n=13 t>7. невозможно представить 26=2*13, (3*13 кратно 3), 4*13, (5*13 кратно 5), (6*13 кратно 6).

Продолжая, по индукции сделаем такой вывод: невозможно представить числа вида
z = 2^i * n, где n — простое, а 2^i < n/2, или i < log2(n)-1.

---

Итого, невозможно представить
z = 2^i, i >= 0
z = 2^i * n, n простое, 1 <= i < log2(n)-1

Вот эти числа
1
2
4
8
16
32
64
128
256
512

{5,7}*2 -- 2
{9,11,13}*{2,4} -- 6
{17,19,23,29,31}*{2,4,8} -- 15
{37,41,43,47,53,59,61}*{2,4,8,16} -- 28
{67,71,73,79,83,87,89,97,101,103,107,109,113}*{2,4,8} -- 24 (верхняя граница: 67*16>1000)
{127,131,137,139,149,151,163,167,173,179,181,191,193,197,199,211,223}*{2,4} -- 34
{227,229,233,239,241,251,257,263,269,271
,277,281,283,293,307,311,313,317,331,337
,347,349,353,359,367,373,379,383,389,397
,401,409,419,421,431,433,439,443,449,457
,461,463,467,479,487,491,499}*2 -- 47

Итого:
9 + 2 + 6 + 15 + 28 + 24 + 34 + 47 = 165 чисел из 1000 невозможно представить суммой последовательных натуральных чисел.

И опять я погнал! Да что ж это делается-то!

Ну, про то, что степени 2 непредставимы — это осталось в силе.

10 = 1+2+3+4
14 = 2+3+4+5
22 = 11*2 = 4+7 + 5+6
44 = 22*2 = 2+9 + 3+8 + 4+7 + 5+6

Короче говоря, рассмотрим сумму четного количества последовательных чисел.
((p-1)+(p)) + ((p-2)+(p+1)) + ... + ((p-q)+(p+q-1)) = q*(2p-1) = (p-q)+...+(p+q-1), 1<=q<p

Т.е. числа вида 2^i * (2p-1) представимы, если 2^i < 2p-1

А, как я уже написал ранее, если z = 2^i * prime и 2^i > prime/2, такие числа можно представить суммой нечетного количества чисел.

Поэтому
Непредставимы только степени 2. В количестве 9 штук на 1000.

Здравствуйте, Кодт, Вы писали:

К>Непредставимы только степени 2. В количестве 9 штук на 1000.

Ну а единичку то Вы за что ? Десять их, а не 9.

А вот (на мой взгляд) чуть более элегантное доказательство:

Сумма последовательных нат. чисел от M+1 до N равна N*(N+1)/2-M*(M+1)/2=(N-M)*(N+M+1)/2.
Для N>(M+1)>0 в этом числе обязательно есть нечетный сомножитель, поэтому оно не может быть степенью двойки.

Если число не есть степень двойки, оно представимо в виде 2^m*(2*n+1) при m,n>0.
Если n>=2^m, то
2^m*(2*n+1) = (n-2^m+1) + ... + (n+2^m),
а если n<2^m, то
2^m*(2*n+1) = (2^m-n) + ... + (2^m+n).
т.е. любой число, кроме степеней двойки нас устраивает (ну и кроме единички )

Следовательно их 990.

Здравствуйте, kfmn, Вы писали:

K>А вот (на мой взгляд) чуть более элегантное доказательство:

С ответом 990 совершенно согласен,
а что касается доказательства,
то каждому, конечно, милее своё

Пусть N можно записать в виде:
N=n+(n+1)+(n+2)+...(n+k-1)=(2n+k-1)k/2        (1)

Или k или 2n+k-1 неминуемо нечётное (и оба они >1 для k>1, n>0). 
Поэтому N обязано иметь по крайней мере 1 нечётный делитель.
Поэтому степени двойки непредставимы точно.

Докажем, что все остальные представимы.
Пусть D - некоторый нечётный делитель N.
Мы имеем один из двух случаев:

1) D-1 < 2N/D

В этом случае выберем k=D 
И из (1) n = (2N/D-(D-1))/2 > 0  

2) D-1 >= 2N/D

Положим 2n+k-1 = D                           (2)
И из (1) k=2N/D
А из (2) n= (D+1-2N/D)/2 > (D-1-2N/D)/2 >= 0

Таким образом мы получили формулы для n>0 (первого члена в сумме) 
и k>1 (числа членов в сумме). Т.е. получили представление 
для любого N и любого её нечётного делителя.

Можно утверждать больше - любой уникальный нечётный делитель 
даёт уникальное разложение N. Это следует из того, что либо мы имеем 
уникальное нечётное число членов в сумме, либо уникальное чётное 
(для уникальных делителей D величины 2N/D тоже уникальны). 
С другой стороны, нет никаких других, неучтённых разложений, 
т.к. из (1) мы можем найти опорный нечётный делитель и указать 
уже подсчитанное разложение. Таким образом, мы доказали, что
число различных разложений равно числу нечётных делителей.

Например, N=90=2*3*3*5 имеет 5 нечётных делителя (3,5,9,15,45) 
и 5 различных разложений.

44+45+46
16+17+18+19+20
6+7+8+9+10+11+12+13+14
2+3+4+5+6+7+8+9+10+11+12+13
21+22+23+24