A111774 Numbers that can be written as a sum of at least three consecutive positive integers.

6, 9, 10, 12, 14, 15, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102

Offset: 1

Author

Jaap Spies, Aug 15 2005

Keywords

• easy
• nonn

Comments

In this sequence there are no (odd) primes and there are no powers of 2.

So we have only three kinds of natural numbers: the odd primes, the powers of 2 and the numbers that can be represented as a sum of at least three consecutive integers.

Odd primes can only be written as a sum of two consecutive integers. Powers of 2 do not have a representation as a sum of k consecutive integers (other than the trivial n=n, for k=1).

Numbers of the form (x*(x+1)-y*(y+1))/2 for nonnegative integers x,y with x-y >= 3. - Bob Selcoe, Feb 21 2014

Numbers of the form (x + 1)*(x + 2*y)/2 for integers x,y with x >= 2 and y >= 1. For y = 1 only triangular numbers (A000217) >= 6 occur. - Ralf Steiner, Jun 27 2019

From Ralf Steiner, Jul 09 2019: (Start)

If k >= 1 sequences are c_k(n) = c_k(n - 1) + n + k - 1, c_k(0) = 0, means c_k(n) = n*(n + 2*k - 1)/2: A000217, A000096, A055998, A055999, A056000, ... then this sequence is the union of c_k(n), n >= 3. (End)

From Wolfdieter Lang, Oct 28 2020: (Start)

This sequence gives all positive integers that have at least one odd prime as proper divisor. The proof follows from the first two comments.

The set {a(n)}_{n>=1} equals the set {k positive integer : floor(k/2) - delta(k) >= 1}, where delta(k) = A055034(k). Proof: floor(k/2) gives the number of positive odd numbers < k, and delta(k), gives the number of positive odd numbers coprime to k. delta(1) = 1 but 1 is not < 1, therefore k = 1 is not a member of this set. Hence a member >= 2 of this set has at least one odd number > 1 and < k missing in the set of odd numbers relative prime to k. Therefore there exists at least one odd prime < k dividing k. (End)

For the multiplicity of a(n) see A338428, obtained from triangle A337940 (the array is given Bob Selcoe as example below, and in the Ralf Steiner comment above). - Wolfdieter Lang, Dec 09 2020

Examples

			a(1)=6 because 6 is the first number that can be written as a sum of three consecutive positive integers: 6 = 1+2+3.
From _Bob Selcoe_, Feb 23 2014: (Start)
Let the top row of an array be A000217(n). Let the diagonals (reading down and left) be A000217(n)-A000217(1),  A000217(n)-A000217(2), A000217(n)-A000217(3)..., A000217(n)-A000217(n-3).  This is A049777 read as a square array, starting with the third column. The array begins as follows:
   6 10 15 21 28 36 45 55 66
   9 14 20 27 35 44 54 65
  12 18 25 33 42 52 63
  15 22 30 39 49 60
  18 26 35 45 56
  21 30 40 51
  24 34 45
  27 38
  30
This is (x*(x+1)-y*(y+1))/2 for nonnegative integers x,y with x-y >= 3, because it is equivalent to 1+2+3/+4/+5/...+x/-0/-1/-2/-3/-4/-5/...-(x+3)/ for all possible strings of consecutive integers, which represents every possible way to sum three or more consecutive positive integers. So for example, 4+5+6+7 = 1+2+3+4+5+6+7-1-2-3 = 22, which is (x*(x+1)-y*(y+1))/2 when x=7, y=3. Notice that values can appear more than once in the array because some numbers can be represented as sums of more than one string of three or more consecutive positive integers. For example, 30 = (x*(x+1)-y*(y+1))/2 when (a) x=11, y=8: 9+10+11; (b) x=9, y=5: 6+7+8+9; and (c) x=8, y=3: 4+5+6+7+8. By definition, x-y is the number of integers in the string. (End)
		

References

• Paul Halmos, "Problems for Mathematicians, Young and Old", Dolciani Mathematical Expositions, 1991, Solution to problem 3G p. 179.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Nieuw Archief voor Wiskunde 5/6 nr. 2 Problems/UWC, Problem C, Jun 2005, p. 181-182.
• Nieuw Archief voor Wiskunde 5/6 nr. 2 Problems/UWC, Problem C: Solution of this Problem
• J. Spies, Sage program for computing A111774

Crossrefs

Cf. A000040, A000079, A066542, A174090 (complement), A000217, A049777, A055034.

Cf. A337940, A338428.

Programs

Maple

ispoweroftwo := proc(n) local a, t; t := 1; while (n > t) do t := 2*t end do; if (n = t) then a := true else a := false end if; return a; end proc; f:= proc(n) if (not isprime(n)) and (not ispoweroftwo(n)) then return n end if; end proc; seq(f(i),i = 1..150);

Mathematica

max=6!;lst={};Do[z=n+(n+1);Do[z+=(n+x);If[z>max,Break[]];AppendTo[lst,z],{x,2,max}],{n,max}];Union[lst] (* Vladimir Joseph Stephan Orlovsky, Mar 06 2010 *)

PARI

isok(n) = !(n == 1) && !isprime(n) && !(isprimepower(n, &p) && (p == 2)); \\ Michel Marcus, Jul 02 2019

Python

from sympy import primepi
def A111774(n):
    def f(x): return int(n+(0 if x<=1 else primepi(x)-1)+x.bit_length())
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Sep 19 2024