Brian Barsotti - cp's OEIS frontend

A331503 a(n) is the number of sets modulo n which can be formed by a finite arithmetic sequence.

1, 3, 7, 15, 31, 42, 99, 119, 193, 218, 463, 340, 807, 682, 849, 1087, 1939, 1299, 2775, 1862, 2615, 3050, 5107, 2988, 5681, 5242, 6439, 5656, 10615, 5562, 13083, 9631, 11367, 12362, 14153, 10531, 22719, 17578, 19361, 16050, 31243, 16728, 36207, 24284, 26133

Offset: 1

Brian Barsotti, May 03 2020

nonn

			For n = 3, the a(3) = 7 solutions are {1}; {2}; {3}; {1,2}; {1,3}; {2,3}; {1,2,3}.

Cf. A000005 (tau), A000203 (sigma).

Array[#3 + #1 (#2 - 1 - 3 #4 + Sum[#1/GCD[#1, i], {i, #4}]) & @@ Join[{#}, DivisorSigma[{0, 1}, #], {Floor[#/2]}] &, 45] (* Michael De Vlieger, May 04 2020 *)

a(n) = {sigma(n) + n*(numdiv(n) - 1 - 3*(n\2) + sum(i=1, n\2, n/gcd(n,i)))} \\ Andrew Howroyd, May 03 2020

a(n) = sigma(n) + n*(tau(n) - 1 - 3*floor(n/2) + Sum_{i=1..floor(n/2)} n/gcd(n,i)).

A332053 a(n) is the number of sets modulo n which can be formed by a finite arithmetic sequence, whose complement cannot be formed by a finite arithmetic sequence.

Original entry on oeis.org

0, 0, 0, 0, 0, 12, 0, 24, 18, 40, 0, 120, 0, 84, 90, 160, 0, 270, 0, 320, 168, 220, 0, 672, 100, 312, 270, 616, 0, 1020, 0, 800, 396, 544, 350, 1656, 0, 684, 546, 1680, 0, 1932, 0, 1496, 1260, 1012, 0, 3168, 294, 1850, 918, 2080, 0, 3132, 770, 3136

Offset: 1

Brian Barsotti, Mar 04 2020

nonn

			One example of such a set would be {0, 2, 4} mod 8. This set can be formed by starting with 0 and adding 2 twice. However, the set's complement, {1, 3, 5, 6, 7} mod 8, cannot be formed by any arithmetic sequence without including the original set.

Cf. A000005 (tau), A000203 (sigma).

a(n)={if(n<=2, 0, n*(sigma(n) - numdiv(n) - n + n%2))} \\ Andrew Howroyd, Mar 05 2020

a(n) = n*(sigma(n) - tau(n) - n + (n mod 2)) for n > 2.

a(p) = 0 for all primes p.

Terms a(31) and beyond from Andrew Howroyd, Mar 05 2020

a(20) corrected by Georg Fischer, Oct 06 2024

A307105 Number of rational numbers which can be constructed from the set of integers between 1 and n, through a combination of multiplication and division.

Original entry on oeis.org

1, 1, 3, 9, 21, 63, 117, 351, 621, 1161, 2043, 6129, 8631, 25893, 45135, 71685, 102285, 306855, 420309, 1260927, 1755513, 2671299, 4571073, 13713219, 17156853, 25778169, 43930755, 59315085, 80765235, 242295705, 295267275, 885801825

Offset: 0

Brian Barsotti, Jul 07 2019

nonn

This sequence can contain only odd terms, because apart from 1, for every term x/y there is always the corresponding terms y/x. - Giovanni Resta, Jul 07 2019
a(n) <= 3*a(n-1), with equality iff n is prime. - Yan Sheng Ang, Feb 13 2020
Conjecture: Let p <= n be prime. If m and p^a*m are two such rationals, then so is p^k*m for all 0 < k < a. - Yan Sheng Ang, Feb 13 2020

			a(2) = 3 because {1,2} can create {1/2, 1, 2}.
a(3) = 9 because {1,2,3} can create {1/6, 1/3, 1/2, 2/3, 1, 3/2, 2, 3, 6}.
a(4) = 21 because {1,2,3,4} can create {1/24, 1/12, 1/8, 1/6, 1/4, 1/3, 3/8, 1/2, 2/3, 3/4, 1, 4/3, 3/2, 2, 8/3, 3, 4, 6, 8, 12, 24}.

Yan Sheng Ang, Table of n, a(n) for n = 0..51

Cf. A018805, A060957.

s:= proc(n) option remember; `if`(n=0, {1},
      map(x-> [x, x*n, x/n][], s(n-1)))
    end:
a:= n-> nops(s(n)):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 29 2019

L={}; s={1}; Do[s = Union[s, s/k, s*k]; AppendTo[L, Length@ s], {k, 13}]; L (* Giovanni Resta, Jul 07 2019 *)

a(p) = 3 * a(p-1), for p prime. - Giovanni Resta, Jul 07 2019

a(9)-a(31) from Giovanni Resta, Jul 07 2019

A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).

Original entry on oeis.org

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

Offset: 1

Brian Barsotti, Jul 29 2019

nonn

Starting with the integers {0, 1, ..., n-1}, a(n) represents the number of times you must apply the function f = (x)-> x^2 mod n to each element of a set in order to reach the smallest possible residue class modulo n.

			Under modulo 5, {0,1,2,3,4} becomes {0,1,4} through the first squaring iteration, which itself becomes {0,1} through the second iteration. This residue class cannot be reduced any further, so a(5) = 2.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A277847.

a:= proc(n) local c, s, i, h; c, s:= n, {$0..n-1};
      for i from 0 do s:= map(x-> irem(x^2, n), s);
        h:= nops(s); if c=h then return i else c:= h fi
      od
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jul 30 2019

a[n_] := Module[{c = n, s = Range[0, n-1], i, h}, For[i = 0, True, i++, s = Mod[#^2, n]& /@ s // Union; h = Length[s]; If[c==h, Return[i], c = h]]];
Array[a, 120] (* Jean-François Alcover, Nov 27 2020, after Alois P. Heinz *)

A308629 Lengths between nodes on a square spiral, such that the n-th node is closer to the (n-2)-th node than to the (n-1)-th node.

Original entry on oeis.org

1, 2, 4, 4, 5, 6, 8, 6, 10, 10, 9, 12, 13, 11, 15, 15, 15, 17, 18, 17, 20, 21, 19, 23, 24, 22, 26, 26, 24, 29, 29, 27, 32, 31, 30, 35, 33, 32, 38, 36, 35, 41, 38, 38, 44, 41, 39, 48, 43, 42, 51, 45, 45, 53, 48, 47, 56, 51, 50, 59, 53, 52, 62, 56, 55, 65, 58

Offset: 1

Brian Barsotti, Jun 11 2019

nonn

Consider a square spiral which begins at the origin and spirals counterclockwise. We define (0, 0) and (1, 0) as the first two nodes. From here, we wish to find the first point along the spiral path which is closer to (0, 0) than to (1, 0). This point would be (0, 1), which is 2 unit lengths away from the previous node. Hence 2 is the first number in our sequence. Likewise, 4 is the next number, as we have to travel 4 unit lengths along the square spiral to reach a point closer to (1, 0) than to (0, 1), and so on.

Based on an empirical observation of the first several terms, I conjecture that lim_{n->infinity} a(n)/n = 8/9.

Brian Barsotti, Square Spiral Illustration
Rémy Sigrist, Scatterplot of the first 1000 nodes
Rémy Sigrist, PARI program for A308629

PARI
```
See Links section.
```

More terms from Rémy Sigrist, Jun 12 2019

cp's OEIS Frontend

User: Brian Barsotti

A331503 a(n) is the number of sets modulo n which can be formed by a finite arithmetic sequence.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A332053 a(n) is the number of sets modulo n which can be formed by a finite arithmetic sequence, whose complement cannot be formed by a finite arithmetic sequence.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A307105 Number of rational numbers which can be constructed from the set of integers between 1 and n, through a combination of multiplication and division.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A308629 Lengths between nodes on a square spiral, such that the n-th node is closer to the (n-2)-th node than to the (n-1)-th node.

Views

Author

Keywords

Comments

Links

Programs

PARI

Extensions