A337940 -id:A337940 - cp's OEIS frontend

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

Jaap Spies, Aug 15 2005

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

			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)

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

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

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

Cf. A337940, A338428.

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);

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 *)

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

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

A219839 a(n) is the number of odd integers in 2..(n-1) that have a common factor (other than 1) with n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 2, 0, 1, 3, 0, 0, 3, 0, 2, 4, 1, 0, 4, 2, 1, 4, 2, 0, 7, 0, 0, 6, 1, 5, 6, 0, 1, 7, 4, 0, 9, 0, 2, 10, 1, 0, 8, 3, 5, 9, 2, 0, 9, 7, 4, 10, 1, 0, 14, 0, 1, 13, 0, 8, 13, 0, 2, 12, 11, 0, 12, 0, 1, 17, 2, 8, 15, 0, 8, 13, 1, 0, 18

Offset: 1

Lei Zhou, Nov 29 2012

a(n) is also the number of linearly dependent diagonal/side length ratios R(n,k), in the regular n-gon. The following will explain this. In the regular n-gon inscribed in a circle the number of distinct diagonals including the side is floor(n/2). Not all of the corresponding length ratios R(n,k) = d(n,k)/d(n,1), k = 1..floor(n/2), with d(n,1) = s(n) (the length of the side), d(n,2) the length of the smallest diagonal, etc., are linearly independent because C(n,R(n,2)) = 0, where C is the minimal polynomial of R(n,2) = 2*cos(Pi/n) (see A187360) with degree delta(n) = A055034(n). Thus every ratio R(n,j), with j = delta(n)+1, ..., floor(n/2) can be expressed as a linear combination of the independent R(n,k), k=1, ..., delta(n). See the comment from Sep 21 2013 on A053121 for powers of R(n,2) (called there rho(N)). Therefore, a(n) = floor(n/2) - delta(n) is, for n>=2, the number of linearly dependent ratios R(n,k) in the regular n-gon. - Wolfdieter Lang, Sep 23 2013
From Wolfdieter Lang, Nov 23 2020: (Start)
This sequence gives the difference between the number of odd numbers in the smallest nonnegative residue system modulo n (called here RS(n)) and the smallest nonnegative restricted residue system (called here RRS(n), but RRS(1) = {1}, not {0}).
This sequence can be used to find sequence A111774 by recording the positions of the entries >= 1. See a W. Lang comment there, and also A337940, for the proof. Hence the complement of A111774, given in A174090, is given by the numbers m with a(m) = 0. (End)

			n=1: there is no odd number greater than 2 but smaller than 1-1=0, so a(1)=0.
Same for n=2,3.
n=4: 3 is the only odd number in 2..(4-1), and GCD(3,4)=1, so a(4)=0.
For any prime numbers and numbers in the form of 2^n, no odd number in 2..(n-1) has common factor with n, so a(p)=0 and a(2^n)=0, n>0.
n=6: 3,5 are odd numbers in 2..(6-1), and GCD(3,6)=3>1 and GCD(5,6)=1, so a(6)=1.
n=15: candidates are 3,5,7,9,11,13.  3, 5, and 9 have greater than 1 common factors with 15, so a(15)=3
From _Wolfdieter Lang_, Sep 23 2013: (Start)
Example n = 15 for a(n) = floor(n/2) - delta(n): 1, 3, 5, 7, 9, 11, 13 take out 1, 7, 9, 11, leaving 3, 5, 13. Therefore, a(15) = 7 - 4 = 3. See the formula above for delta.
In the regular 15-gon the 3 (= a(15)) diagonal/side ratios R(15, 5), R(15, 6) and R(15,7) can be expressed as linear combinations of the R(15,j), j=1..4.  See the n-gon comment above. (End)
From _Wolfdieter Lang_, Nov 23 2020: (Start)
n = 1: RS(1) = {0}, RRS(1) = {1}, hence a(1) = 0 - 1 = 0. Here RRS(1) is not {0}(standard) because delta(1) := 1 (the degree of minimal polynomial for 2*cos(Pi//1) = -2 which is x+2, see A187360).
n = 6: RS(6) = {0, 1, 2, 3, 4, 5} and RRS(6) = {1,5}, hence a(6) = 3 - 2 = 1, and A111774(1) = 6 = A337940(1, 1).
a(15) = 7 - 4 = 3, and A111774(6) = 15 = A337940(3, 3) = A337940(4, 1) (multiplicity 2 = A338428(6)). (End)

Lei Zhou, Table of n, a(n) for n = 1..10000

Cf. A000010, A016035 (see 1st comment there), A004526, A055034, A111774, A174090, A190357, A337940, A338428.

Table[Count[Range[3, n - 1, 2], ?(GCD[n, #] > 1 &)], {n, 100}] (* _T. D. Noe, Nov 30 2012 *)
a[1] = 0; a[n_] := Floor[n/2] - EulerPhi[2*n]/2; Array[a, 80] (* Amiram Eldar, Nov 28 2020 *)

a(n) = sum(i=2, n-1, (i%2) && (gcd(i,n)!=1)); \\ Michel Marcus, Aug 07 2018

a(n) = floor(n/2) - delta(n), with floor(n/2) = A004526 and delta(n) = A055034(n) = phi(2*n)/2, for n >= 2, with Euler's phi A000010. See the Aug 17 2011 comment on A055034. For n = 1 this would be -1, not 0, because delta(1) = 1. - Wolfdieter Lang, Sep 23 2013

Sum_{k=1..n} a(k) ~ c*n^2, where c = 1/4 - 2/Pi^2 = 0.04735763... (A190357). - Amiram Eldar, Feb 23 2025

A338428 Multiplicities for A111774(n), for n >= 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1, 2, 2, 1, 2, 1, 3, 1, 4, 1, 1, 1, 2, 2, 1, 3, 2, 1, 2, 1, 3, 1, 4, 2, 3, 1, 2, 3, 2, 1, 4, 1, 2, 3, 1, 3, 1, 3, 2, 1, 2, 1, 5, 2, 1, 2, 1, 2, 1, 2, 4, 1

Offset: 1

Wolfdieter Lang, Nov 23 2020

nonn

See the triangle and array of A337940 for details.

The first n and N(n) = A111774(n) with multiplicity m are [m, n, N] = [1, 1, 6], [2, 6, 15], [3, 16, 30], [4, 26, 45], [5, 60, 90], [6, 72, 105], [7, 157, 210], ...

			For a(6) = 2 for  A111774(6) = 15 see the example given in A337940.
Similarly for a(24) = 3 for A111774(24) = 42.

Cf. A111774, A337940.

a(n) gives the number of possibilities to write A111774(n) as a sum of at least three consecutive positive integers.

A337939 Irregular triangle T(n, m) read by rows: row n gives the distinct length ratios diagonal/side of regular n-gons, DSR(n, k), for n >= 2, k = 1, 2, ..., floor(n/2), expressed by the coefficients in the power basis of the Galois group Gal(Q(rho(n))/Q), where rho(n) = 2*cos(Pi/n), for n >= 2. T(1, 1) is set to 1.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, -1, 0, 1, 1, 0, 1, -1, 0, 1, 0, -2, 0, 1, 1, 0, 1, -1, 0, 1, 1, 1, 1, 0, 1, -1, 0, 1, 0, -2, 0, 1, -4, 0, 2, 1, 0, 1, -1, 0, 1, 0, -2, 0, 1, 1, 0, -3, 0, 1, 1, 0, 1, -1, 0, 1, 0, -2, 0, 1, 0, 0, 1, 0, 2

Offset: 1

Wolfdieter Lang, Jan 15 2021

The length of row n is given in A338431(n), for n >= 1.
The length of the sublists t(n, k) of the power basis coefficients of DSR(n, k), for k = 1, 2, ..., floor(n/2), is 1 if n = 1, for n >= 2 it is k except for n = n(j) = A111774(j) for which the final A219839(n) sublists have fewer than k members.
Trailing vanishing coefficients of the delta(n) = A055034(n) power base elements <1 = rho(n)^0, rho(n)^1, ..., rho(n)^{delta(n)-1}> are not recorded. The coefficients of the minimal polynomial C(n, x) of rho(n) = 2*cos(Pi/n) of degree delta(n) are given in A187360. C(n, rho(n)) = 0 is used to eliminate all powers of rho with exponent >= delta(n).
The length ratios DSR(n, k) := diagonal(n, k)/side(n) of regular n-gons, for n >= 2, and k = 1, 2, ..., floor(n/2) (distinct diagonals, starting with the side for k = 1, in increasing order) are given by DSR(n, k) = S(k-1, rho(n)), with the Chebyshev S polynomials (A049310). See the W. Lang link.
For n = 2, the degenerate case, diagonal/side = side/side = 1 for k = 1. For n = 1 (a point) diagonal/side is undetermined, and T(1, 1) is set to 1.
For the power basis sublists t(n, k), for k = 1, 2, ..., delta(n), only the k coefficients of S(k-1, x) are present (trailing vanishing coefficients are not recorded). For k = delta(n)+1, ..., floor(n/2) less than k coefficients appear due to elimination via C(n, rho(n)) = 0. E.g., for n = 6 with delta(6) = 2 the only coefficient for k = 3 is 2 (coefficient of rho^0). This appears for n = n(j) = A111774(j), because then floor(n/2) - delta(n) = A219839(n) > 0.
Because A219839(n) = 0 means that n is from A174090, i.e., a prime or a power of 2 (complement of A111774), these rows n have all the sublists t(n, k) with the k coefficients of S(k-1, x), hence they are identical (but the basis differs). See especially the table for the pairs of consecutive numbers n with identical coefficients, like (2, 3), (4, 5), (16, 17), (256, 267), (65536, 65537), ?... (cf. Fermat primes A019434).

			The irregular triangle T(n, m) begins: (For n >= 4 the bar divides the DSR(n, k) power basis coefficients, the sublists t(n, k), for k = 1, 2, ..., floor(n/2))
n \ m  1   2 3    4  5  6   7  8 9 10   11 12 12  13 14  15 16 17 18 19 20 ...
1:     1
2:     1
3:     1
4:     1 | 0 1
5:     1 | 0 1
6:     1 | 0 1 |  2
7:     1 | 0 1 | -1  0  1
8:     1 | 0 1 | -1  0  1 | 0 -2 0  1
9:     1 | 0 1 | -1  0  1 | 1  1
10:    1 | 0 1 | -1  0  1 | 0 -2 0  1 | -4  0  2
11:    1 | 0 1 | -1  0  1 | 0 -2 0  1 |  1  0 -3   0  1
12:    1 | 0 1 | -1  0  1 | 0 -2 0  1 |  0  0  1 | 0  2
13:    1 | 0 1 | -1  0  1 | 0 -2 0  1 |  1  0 -3   0  1 | 0  3  0 -4  0  1
...
n = 14: 1 | 0 1 | -1 0 1 | 0 -2 0 1 | 1 0 -3 0 1 | 0 3 0 -4 0 1 | 6 0 -8 0 2,
n = 15: 1 | 0 1 | -1 0 1 | 0 -2 0 1 | 0 4 1 -1 | 1 -2 0 1 | -1 1 1,
n = 16 and n = 17: 1 | 0 1 | -1  0 1 | 0 -2 0 1 | 1 0 -3 0 1 | 0 3 0 -4 0 1 | -1 0 6 0 -5 0 1 | 0 -4 0 10 0 -6 0 1,
--------------------------------------------------------------------------------
n = 5: DSR(5, 1) = 1 = side(5)/side(5), DSR(5, 2) = 1*rho(5) = A001622 (golden section).
n = 8: DSR(8, 1) = 1 = side(8)/side(8), DSR(8, 2) = 1*rho(8) = sqrt(2+sqrt(2)) = A179260, DSR(8, 3) = -1 + rho(8)^2 = 1 + sqrt(2) = A014176, DSR(8, 4) = -2*rho(8) + 1*rho(8)^3 = sqrt(2)*rho(8) = A121601.

Wolfdieter Lang, The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon, arXiv:1210.1018 [math.GR], 2012-2017.

Cf. A001622, A055034, A014176, A049310, A019434, A111774, A121601, A179260, A187360, A219839, A338429, A337940, A338431.

T(1, 1) = 1, and in row n, for n >= 2, the power base coefficients of Gal(Q(2*cos(Pi/n))/Q) for DSR(n, k) := diagonal(n, k)/side(n) of regular n-gons, for k = 1, 2, ..., floor(n/2), are listed as t(n, k) in this order, with trailing vanishing coefficients omitted.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

A219839 a(n) is the number of odd integers in 2..(n-1) that have a common factor (other than 1) with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A338428 Multiplicities for A111774(n), for n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula