Сумма последовательных нечетных чисел

24

Несмотря на то, что были заданы соответствующие проблемы , этот вопрос отличается от собственного вопроса.


Вызов

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

Тестовые случаи

  1 -> [1]
  2 -> []
  3 -> [3]
  4 -> [1, 3]
  5 -> [5]
  6 -> []
  9 -> [1, 3, 5] (обратите внимание, что [9] не является правильным ответом)
 15 -> [3, 5, 7]
104 -> [23, 25, 27, 29] (обратите внимание, что [51, 53] не является правильным ответом)

счет

Это , поэтому выигрывает самый короткий ответ на каждом языке.

musicman523
источник
2
Может ли моя программа работать вечно, если нет решения?
Деннис
Очень связано . Тот факт, что некоторые четные числа не могут быть представлены в этом, может спасти его от обмана.
ETHпродукция
6
15 не может дать [-1, 1, 3, 5, 7]? Если разрешены только положительные значения, вы должны сказать это.
xnor
2
@ ЕвгенийНовиков ты пропустил 17
kalsowerus
1
@kalsowerus да. Я неправильно понимаю слово "последовательный"
Евгений Новиков

Ответы:

11

Haskell, 67 65 63 62 58 байт

Сохранено 4 байта благодаря Julian Wolf

f x=[[2*n+1,2*n+3..2*m]|n<-[0..x],m<-[n..x],m^2-n^2==x]!!0

Попробуйте онлайн!

Я проверяю , если число может быть выражено как он разность двух квадратов: m^2-n^2. Затем я могу построить список последовательных нечетных чисел: [2n+1,2n+3...2m-1]. Обратите внимание, что поскольку nвыбран минимум, будет выведен самый длинный список

H.PWiz
источник
7
Отрицатель: было бы более дружелюбным и более конструктивным добавить комментарий с указанием причины, особенно при голосовании нового пользователя.
Джонатан Аллан
1
Если я что-то не упустил, вы можете сэкономить 4 байта, увеличивая только до xобоих, nиm
Джулиан Вольф
Точно так же, вы знаете, что пользователь сообщества автоматически произнес отрицательный ответ, когда вы отредактировали свой ответ. Я считаю это ошибкой . (CC @JonathanAllan)
Деннис
Ааа, это был один из них.
Джонатан Аллан
9

Python 2 , 66 62 байта

f=lambda n,k=0,*r:n-sum(r)and f(n,k+1,*range(k%n|1,k/n,2))or r

Выход с RuntimeError (превышена максимальная глубина рекурсии), если нет решения.

Попробуйте онлайн!

Деннис
источник
1
Если входные значения достаточно высоки, но есть решение, приведет ли это к RuntimeError ?
Okx
Если предел рекурсии недостаточно высок и / или стек не достаточно велик, да. Тем не менее, обычно игнорируют физические ограничения (например, ответ C должен работать только для 32-битных целых), и OP явно сказал, что выполнение навсегда приемлемо, если нет решения.
Деннис
9

Желе ,  11  10 байт

-1 байт благодаря Деннису (используйте неявное построение диапазона - замените Rm2Ẇна ẆḤ’)

ẆḤ’S_¥Ðḟ⁸Ṫ

Монадическая ссылка, возвращающая список слагаемых, если возможно, или 0если нет.

Попробуйте онлайн!

Как?

ẆḤ’S_¥Ðḟ⁸Ṫ - Link: number, n
Ẇ          - all sublists (implicit range of input) note: ordered by increasing length
           -                i.e. [[1], [2], [3], ..., [1,2], [2,3], ..., [1,2,3], ...]]
 Ḥ         - double              [[2], [4], [6], ..., [2,4], [4,6], ..., [2,4,6], ...]]
  ’        - decrement           [[1], [3], [5], ..., [1,3], [3,5], ..., [1,2,5], ...]]
        ⁸  - link's left argument, n
      Ðḟ   - filter out items for which the following yields a truthy value:
     ¥     -   last two links as a dyad:
   S       -     sum
    _      -     subtract the right from the left = sum - n
         Ṫ - tail (last and hence longest such run)
Джонатан Аллан
источник
1
ẆḤ’сохраняет байт.
Деннис
8

JavaScript (ES7), 87 86 85 81 байт

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

n=>(g=(s,k,x=n+s)=>(x**.5|0)**2-x?k>n?0:g(s+k,k+2):(n-=k)?k+','+g(-n,k+2):k)(0,1)

Как?

Сначала мы ищем наименьший идеальный квадрат s , так что x = n + s - еще один идеальный квадрат.

Если s существует, n является разностью x - s 2 совершенных квадратов, которая может быть записана как разность 2 последовательностей последовательных нечетных чисел. Затем мы строим полученный список.

Пример:

Для n = 104 :

Мы находим s = 11² = 121, который удовлетворяет x = n + s = 225 = 15²

Затем:

15² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 + 29
11² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21
104 = 15² - 11² = 23 + 25 + 27 + 29

Arnauld
источник
3
Подождите, вы говорите мне, что n^2всегда равна сумме первых nнечетных чисел?
Да
2
@ Mayube Действительно !
Арно
7

05AB1E , 9 8 байт

-1 байт благодаря Emigna

ÅÉŒʒOQ}н

Объяснение:

ÅÉ           Generate a list of odd numbers up to, and including, the input
  Œ          Substrings
   ʒ         Only keep values
    O          where the sum
     Q         equals the input
       }     End
             For 9, the result would look like this:
             [[1, 3, 5], [9]]
        н    Get the first value

При неверном вводе ничего не выводится.

Попробуйте онлайн!

Okx
источник
ʒOQ}вместо того, чтобы DO¹QÏсохранить байт.
Эминья
@JonathanAllan Docs говорят «неровно», так что это могло бы привести в замешательство ...
Эрик Игрок в гольф
1
@JonathanAllan Маленькая ошибка. Исправлена.
Okx
6

Haskell , 61 60 байт

Спасибо @maple_shaft за сбривание 1 байта

f n=[k|r<-[1,3..],s<-[r,r+2..n],k<-[[r,r+2..s]],sum k==n]!!0

Попробуйте онлайн!

Используется тот факт, что самым длинным пробегом всегда будет запуск, начинающийся с наименьшего числа.

Я хотел сделать что-то с арифметикой вместо грубого принуждения k, но, fromIntegerпохоже, убил это.

Юлианский волк
источник
Вы можете сэкономить один байт, изменив [1,3..n]на[1,3..]
maple_shaft
1
Вы можете сохранить 7 байтов с помощью вспомогательной функции r?n=[r,r+2..n]. Попробуйте онлайн!
Орджан Йохансен
4

Python , 67 байт

f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+2],R[1:]][sum(R)>n])or R

Попробуйте онлайн!

Я скопировал мой ответ от предыдущей последовательной вызов суммы и изменил +1к +2. Кто знал, что гольф-код может быть таким модульным?

Странно простая стратегия: ищите интервал Rс желаемой суммой.

  • Если сумма слишком мала, сдвиньте правую конечную точку интервала вверх на 2, добавив следующую цифру 2 над ней.
  • Если сумма слишком велика, сдвиньте левую конечную точку, удалив наименьший элемент
  • Если сумма верна, выведите R.

Поскольку нижний конец интервала только увеличивается, более длинные интервалы находятся перед более короткими. Если возможный интервал не может быть найден, завершается с помощью IndexError.

XNOR
источник
4

JavaScript (ES6), 65 64 байта

f=(a,i=1)=>a>i?(c=f(a-i,i+=2))[0]==i?[i-2,...c]:f(a,i):a<i?0:[i]

Возвращает массив, если есть решение, или 0, если нет решения.

Это очень неэффективный, но гольф решение проблемы.

Он ищет первое решение, используя a-iи i=1, даже если не работает рекурсивный стек. Если это решение не начинается с i+2, то мы рекурсивно ищем первое решение, используя aи i+2.

Ungolfed

f=(a,i=1)=>
  a > i ? 
    (c = f(a - i, i += 2))[0] == i ? 
      [i-2, ...c] : 
      f(a, i) :
  a < i ? 
    0 :
    [i]

Тестовые случаи:

Чтобы понять, насколько это неэффективно, решение f(104)требует 69 535 рекурсивных вызовов. Глубина стека никогда не превышает 51 уровня, поэтому проблем с переполнением стека нет.

Решение f(200)требует 8,6 миллионов рекурсивных вызовов со стеком в 99 уровней. (Его решение есть [11,13,15,17,19,21,23,25,27,29].)

Вот визуальное представление работающей программы:

Рик Хичкок
источник
3

Python 2.7, 109 108 97 байт

11 байтов вниз, благодаря Эрику Outgolfer.

Это мой первый кодовый гольф!

def f(N):
 for n in range(N):
    x=(n*n+N)**.5-n
    if x%1==0:return[2*(k+n)+1for k in range(int(x))]

Как это работает

Я использовал хорошо известную личность, которая 1 + 3 + 5 + ... + (2n - 1) = n²

Возьмите случай 15

15 = 3 + 5 + 7 = (1 + 2) + (3 + 2) + (5 + 2) = (1 + 3 + 5) + 3×2 = 3² + 3×2

В общем, если есть х терминов , начиная с 2n + 1, как

(2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1))


Равно 2nx + x²

Если Nвходное целое число, проблема сводится к тому, чтобы найти максимум xтаким, чтобы

x² + 2nx - N = 0

Это квадратное уравнение с решением

x = sqrt(n² + N) - n

Самая длинная последовательность - самая длинная x. Программа выполняет итерацию nот 0до Nи, когда она находит xэто целое число, она создает список (2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1))и возвращает его.

dark32
источник
@EriktheOutgolfer, спасибо, я забыл об использовании вкладок (=
dark32
3

Python 3, 190 81 байт

def c(q,l,i):
    if sum(l)0:
        l.append(i)
        return c(q,l,i+2)
    elif sum(l)>q:
        l.pop(0)
        return c(q,l,i)
    else:
        print(l)
c(q,[1],1)

c=lambda q,l=[1]:c(q,l+[l[-1]+2])if(sum(l)<q)*l else c(q,l[1:])if sum(l)>q else l

Благодаря @ovs и @ musicman523

Саймон
источник
4
Вы можете уменьшить это до 122 байтов, просто удалив некоторые отступы . Если вы хотите еще больше сократить свой код, ознакомьтесь с советами по игре в гольф на Python .
овс
3
Это не работает в Python 3, потому что в вызове printотсутствуют скобки
musicman523
2
Вы можете удалить l.append(i), просто используя l+[i]в рекурсивном вызове. Вы можете удалить l.pop(0)с помощью l[1:]рекурсивного вызова. Вы можете удалить вызов cв самом низу, используя вместо этого ключевые аргументы. Вы можете удалить >0в строке 2. Наконец, вы можете изменить свои выражения ifи elseв выражения, используя троичную форму, которая сокращает до 92 байтов в качестве лямбда-выражения. Попробуйте онлайн!
musicman523
1
Основываясь на предложениях @ musicman523, мы все еще можем сократить условия и уменьшить iих до 81 байта .
овс
Я думаю , что вы могли бы изменить , sum(l)>q elseчтобы q<sum(l)elseспасти 1 байт.
Захари
2

QBIC , 47 байт

{_Cg=q┘q=q+2~g>:|_Xp\?g,[q,a,2|?b,┘g=g+b~g=a|_X

Это пытается посчитать все нечетные числа от одного до его суммы n. Если оно прошло n, сбросьте цикл, увеличьте 1 до 3 и попробуйте снова. Выйти, печатая 0, если в начале цикла наш номер > n.

объяснение

{       Do infinitely
_C      Clear the screen (we basically print every run of odd numbers, but clear out everything that doesn't sum up to n)
g=q     Set g to the first num of this cycle (q starts as 1 in QBIC)    
┘       (Syntatcic linebreak)
q=q+2   Raise q to the next odd number, this sets up both the next outer loop as well as a coming FOR loop
~g>:|   If we start out with a number > n (read as 'a' from the cmd line)
_Xp     THEN quit, printing 0 (the value of the number var 'p')
\       ELSE
[q,a,2| FOR b = q, b <= n, b+=2
?b,┘    PRINT b followed by a tab
g=g+b   Add 'b' to running total 'g'
~g=a|   and if that lands us on 'n'
_X      QUIT (printing nothing: everything is already printed)
steenbergh
источник
1

R , 90 байт

f=function(x,y=1)'if'(length(w<-which(cumsum(r<-y:x*2-1)==x)),r[1:w],'if'(y>x,0,f(x,y+1)))

Попробуйте онлайн!

Использует рекурсивную функцию, которая тестирует последовательность накопленной суммы y: x, преобразованную в последовательность нечетных чисел. y увеличивается на каждую рекурсию, пока не превысит x. Первая последовательность, которая суммируется с целью, будет возвращена.

MickyT
источник
1

Python 2 , 89 байт

lambda n,r=range:[v for v in[r(1,n+1,2)[i:j]for i in r(n)for j in r(n+1)]if sum(v)==n][0]

Безымянная функция принимает положительное целое число nи возвращает результат, если он существует, и возвращает значение IndexErrorиначе.

Попробуйте онлайн!

Создает список всех соответствующих нечетных чисел, с r(1,n+1,2)которыми есть range(start=1, stop=n+1, step=2); создает все соответствующие субсрезы (плюс несколько пустых), нарезая их от iвключающих до jисключающих с [i:j]поперек iв [0, n), используя r(n)и jв [0, n] используя r(n+1)(пустые, когда i>=jили iвыходит за пределы); фильтры для тех с правильной суммой с if sum(v)==n; возвращает первый (и, следовательно, самый длинный) такой срез, используя [0].

Джонатан Аллан
источник
1

PHP , 73 байта

нет решения бесконечный цикл

for($e=-1;$s-$i=$argn;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n);

Попробуйте онлайн!

PHP , 83 байта

ничего не печатает без решения

каждый мод ввода 4 == 2 не имеет решения

for($e=-1;($i=$argn)%4-2&&$s-$i;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n);

Попробуйте онлайн!

Йорг Хюльсерманн
источник
не удается обнаружить неразрешимый ввод
Тит
@ Титус исправлен ...
Йорг Хюльсерманн
0

Python 2 , 122 121 119 115 байтов

-1 байт благодаря musicman523. -4 байта благодаря Step Hen. ха - ха

def f(n,R=range):r=R(1,n,2);print[i for w in R(1,len(r)+1)for i in[r[j:j+w]for j in R(len(r)-w+1)]if sum(i)==n][-1]

Попробуйте онлайн!

totallyhuman
источник
1
Это на один байт короче как функция. Попробуйте онлайн!
musicman523
Сохраните байты, если вы переопределите range, попробуйте онлайн!
Стивен
Это не для 1 .
Деннис
0

Python 3 , 93 байта

lambda n,r=range:[[*r(s,e+1,2)]for s in r(1,n+1,2)for e in r(s,n+1,2)if(s+e)*(2+e-s)==4*n][0]

Попробуйте онлайн!

Единственное особенное, что я сделал, было отметить, что (s+e)*(2+e-s)==4*nэто эквивалентно sum(range(s,e+1,2))==n, и хотя они имеют одинаковый размер, тогда r=rangeкак первое можно поместить ближе к ifутверждению.

С МакЭвой
источник
0

Python 3 , 185 байт

def f(s):
  d={k:v for k,v in{a:(1-a+((a-1)**2+4*s)**(.5))/2 for a in range(1,s,2)}.items()if int(v)==v};m=max(d.keys(), key=(lambda k: d[k]));return list(range(int(m),int(m+2*d[m]),2))

Попробуйте онлайн!


Что касается того, как это работает, я попытался найти более элегантное решение, чем простой перебор. Я переставил формулу для суммы арифметической последовательности и применил квадратную формулу, чтобы получить выражение (1-a+((a-1)**2+4*s)**(.5))/2, которое появляется в коде. Что вычисляет выражение, учитывая желаемую сумму sи первый член для арифметической последовательностиa , длине последовательности. Эти длины хранятся в словаре как значения для первых терминов в качестве ключей.

Затем все нецелочисленные значения удаляются из словаря, поскольку они представляют недопустимые последовательности. Оттуда наибольшее значение идентифицируется max(d.keys(), key=(lambda k: d[k]))и последовательность нечетных чисел в этой позиции и на этой длине делается с list(range(int(m),int(m+2*d[m]),2)).


Я ищу помощь в игре в гольф, если вы видите что-нибудь. Меня больше интересовало, насколько хорошо я могу справиться с нетривиальным алгоритмом; мой ответ почти вдвое длиннее, чем лучшее решение Python.

Чейз Вогели
источник
Будет ли это работать? repl.it/JTt7 (177 байт)
Захари
0

Mathematica, 56 байт

Last@Cases[Subsequences@Table[n,{n,1,#,2}],x_/;Tr@x==#]&

Functionс первым аргументом #. Table[n,{n,1,#,2}]вычисляет список положительных нечетных чисел, меньших или равных #. Subsequencesвозвращает все подпоследовательности этого списка, упорядоченные по возрастанию длины. Затем мы берем те, Casesкоторые соответствуют x_/;Tr@x==#, то есть последовательности x, так что их сумма Tr@xравна входу #. Затем мы возьмем Lastтакую ​​последовательность.

ngenisis
источник
0

JavaScript (ES6), 72 байта

n=>(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?l+' '+g(s,l+=2):u)(n-1,l=u=1)

Возвращает разделенную пробелами строку нечетных чисел или выбрасывает неверный ввод. 84-байтовая версия, которая возвращает (пустой при необходимости) массив:

n=>n%4-2?(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?[l,...g(s,l+=2)]:[u])(n-1,l=u=1):[]

Объяснение: Свободно основано на awk-решении @ Cabbie407 для сумм последовательных целых чисел, за исключением того, что мне удалось сэкономить несколько байтов с помощью рекурсии.

Нил
источник
0

PHP, 78 байт

for($b=-1;$s-$argn;)for($n=[$s=$x=$b+=2];$s<$argn;)$s+=$n[]=$x+=2;print_r($n);

бесконечный цикл, если нет решения. вставка?$b>$argn+2?$n=[]:1:0 после, $s-$argnчтобы напечатать пустой массив вместо.

Запустите -nRили попробуйте онлайн .

Titus
источник
0

C # (.NET Core) , 129 байт

(i)=>{int s,j,b=1,e=3;for(;;){var o="";s=0;for(j=b;j<e;j+=2){s+=j;o+=j+" ";}if(s==i)return o;s=s<i?e+=2:b+=2;if(b==e)return"";}};

Выводит числа в строку, разделенные пробелом (любой другой символ просто потребует изменения " " ). Ввод без решения возвращает пустую строку (хотя если вечный запуск без ошибок является допустимым способом указать отсутствие решения, то 17 байтов можно сохранить, удалив if(b==e)return"";).

Алгоритм это:

  1. Начните с [1]
  2. Если сумма равна цели, вернуть список
  3. Если сумма меньше целевой, добавьте следующее нечетное число
  4. Если сумма больше, чем цель, удалите первый элемент
  5. Если список пуст, верните его
  6. Повторите с 2
Камил Дракари
источник
Вы можете написать (i)=>какi=>
aloisdg говорит восстановить Monica
0

C ++, 157 -> 147 байт


-10 байт благодаря DJMcMayhem

вернет 0, если нет ответа, 1 в противном случае

последняя строка, которую он печатает, является ответом

int f(int n){for(int i=1;;i+=2){int v=0;for(int k=i;;k+=2){v+=k;std::cout<<k<<" ";if(v==n)return 1;if(v>n)break;}if(i>n)return 0;std::cout<<"\n";}}

ungolfed:

int f(int n)
{
    for (int i = 1;; i += 2)
    {
        int v = 0;
        for (int k = i;; k += 2)
        {
            v += k;
            std::cout << k << " ";
            if (v == n)
                return 1;
            if (v > n)
                break;

        }
        if (i > n)
            return 0;
        std::cout << "\n";
    }
}

это мой первый код гольф ^^

SeeSoftware
источник
Вы могли бы сохранить несколько байтов, если сделали функцию int и вернули 0 или 1. Кроме того, вы могли бы сделать int v=0;вместо int v;....v=0;и, если вы сделали вывод Newline с разделителями, вы могли бы сделать, std::cout<<k<<"\n";а затем вообще удалить второй
Newline
Если я выполнил последнюю рекомендацию, он напечатал бы новую строку для каждого номера, но я хочу разделить группы номеров, но в любом случае спасибо за -10 байт
SeeSoftware
0

Котлин, 152 байта

fun f(a:Double){var n=Math.sqrt(a).toInt()+1;var x=0;while(n-->0){if(((a/n)-n)%2==0.0){x=((a/n)-n).toInt()+1;while(n-->0){println(x.toString());x+=2}}}}

Попробуйте онлайн (подождите 4-5 секунд, компилятор работает медленно)

Ungolfed

fun f(a: Double){
    var n=Math.sqrt(a).toInt()+1;
    var x=0;

    while(n-->0){
        if(((a/n)-n)%2==0.0){
            x=((a/n)-n).toInt()+1;

            while(n-->0){
                println(x.toString());
                x+=2;
            }

        }
    }
}
Евгений Новиков
источник
0

Excel VBA, 139 байт

Subподпрограмма, которая принимает входные данные nожидаемого целого числа и сообщает в ячейку самую длинную последовательность последовательных нечетных чисел[A1]

Sub a(n)
For i=1To n Step 2
s=0
For j=i To n Step 2
s=s+j
If s=n Then:For k=i To j-1 Step 2:r=r &k &"+":Next:[A1]=r &j:End
Next j,i
End Sub
Тейлор Скотт
источник