A290447 -id:A290447 - cp's OEIS frontend

A039655 Number of iterations of f(x) = sigma(x)-1 applied to n required to reach a prime, or -1 if no prime is ever reached.

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

Offset: 2

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
MathOverflow, Does iterating a certain function related to the sums of divisors eventually always result in a prime value?, 2014
Hugo Pfoertner, Terms a(2)...a(1000000).
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A039654, A039649, A039650, A039651, A039652, A039653, A039655, A039656.

For records see A292114 and A292115.

f[n_] := Plus @@ Divisors@n - 1; g[n_] := Length@ NestWhileList[ f@# &, n, !PrimeQ@# &] - 1; Table[ g@n, {n, 2, 106}] (* Robert G. Wilson v, May 07 2010 *)

a(n)=my(t);while(!isprime(n),n=sigma(n)-1;t++);t \\ Charles R Greathouse IV, Sep 16 2014

Escape clause added by N. J. A. Sloane, Aug 31 2017

A292105 Irregular triangle read by rows: T(n,k) = the number of interior points that are the intersections of exactly k chords in the configuration A006561(n) (n >= 1, k >= 1).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 5, 0, 12, 1, 0, 35, 0, 40, 8, 1, 0, 126, 0, 140, 20, 0, 1, 0, 330, 0, 228, 60, 12, 0, 1, 0, 715, 0, 644, 112, 0, 0, 0, 1, 0, 1365, 0, 1168, 208, 0, 0, 0, 0, 1, 0, 2380, 0, 1512, 216, 54, 54, 0, 0, 0, 1, 0, 3876, 0, 3360, 480, 0, 0, 0, 0, 0, 0, 1, 0, 5985

Offset: 1

N. J. A. Sloane, Sep 14 2017

			Triangle begins:
  0;
  0;
  0;
  0,   1;
  0,   5;
  0,  12,  1;
  0,  35;
  0,  40,  8,  1;
  0, 126;
  0, 140, 20,  0, 1;
  0, 330;
  0, 228, 60, 12, 0, 1;
See the attached text file for the first 100 rows.

Seiichi Manyama, Rows n = 1..250, flattened
B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, arXiv:math/9508209 [math.MG], 1995-2006, which has fewer typos than the SIAM version.
B. Poonen and M. Rubinstein, Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. Discrete Mathematics, Vol. 11, pp. 135-156 (1998). [Copy on SIAM web site]
B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, SIAM J. on Discrete Mathematics, Vol. 11, No. 1, 135-156 (1998). [Copy on B. Poonen's web site]
B. Poonen and M. Rubinstein, Mathematica programs for A006561 and related sequences
N. J. A. Sloane, Summary table for vertices and regions in regular n-gon with all chords drawn, for n = 3..19. [V = total number of vertices (A007569), V_i (i>=2) = number of vertices where i lines cross (A292105, A292104, A101363); R = total number of cells or regions (A007678), R_i (i>=3) = number of regions with i edges (A331450, A062361, A067151).]
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
Scott R. Shannon, Table for n=1..100.
Scott R. Shannon, Image of 8-gon.
Scott R. Shannon, Image of 9-gon.
Scott R. Shannon, Image of 12-gon.

Columns give A292104, A101363 (2n-gon), A101364, A101365.
Row sums give A006561.
Cf. A335102.

a(27) and beyond by Scott R. Shannon, May 15 2022

A291792 Numbers m such that Post's tag system started at the word (100)^m eventually dies (i.e., reaches the empty string).

Original entry on oeis.org

5, 13, 14, 22, 25, 46, 47, 54, 63, 65, 70, 74, 78, 80, 91, 93, 106, 110, 117, 118, 128, 144, 148, 160, 166, 169, 190, 195, 199, 209, 222, 229, 234, 236, 239, 240, 243, 252, 254, 263, 264, 265, 266, 278, 281, 283, 286, 302, 304, 310, 324, 326, 327, 336, 339

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

These are the numbers m such that A291793(m)=0, or equivalently A284121(m)=1.
Comments from Lars Blomberg on the method used in calculating the terms, Sep 14 2017: (Start)
Here is an overview of the method I have been using.
Build the words in a large byte array. Each iteration just adds 00 or 1101 to the end and removes 3 bytes from the beginning, without moving the whole word, just keeping track of the length of the word and where it starts within the array.
When the word reaches the end of the array it is moved to the beginning. This allows for very fast iterations, as long as the word is substantially shorter than the array.
The size of the byte array is 10^9, this is the longest word we can handle.
As for cycle detection, the words at iterations A: k*10^5 and B: (k+1)*10^5 are saved.
For iterations above B when the current word has the same length as B (a fast test), then check if the current word is equal to the one at B. If so, we have a cycle whose length can be determined simply by continued iterating. When the current iteration reaches C: (k+2)*10^5, move B->A, C->B, and continue.
The cycle has started somewhere between A and B and we know the cycle length. So restart two iterations at A and initially iterate one of them by the cycle length. Then iterate the two in parallel (being a cycle length apart) until they are equal, which gives the start of the cycle. Only the two words being iterated need to be stored.
One drawback with this method is that it cannot detect a cycle longer than 10^5 (or whatever value we choose). In that case the iterations will go on forever.
(End)
The trajectory of the word (100)^m for m=110 dies after 43913328040672 iterations, so 110 is a term in this sequence. The longest word in the trajectory is 31299218, which appeared at iteration 14392308412264. - Lars Blomberg, Oct 04 2017

Lars Blomberg, Table of n, a(n) for n = 1..1100
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
N. J. A. Sloane, Maple code for A291792, A284119, A291793, A284121, A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part 1, Part 2, Slides. (Mentions this sequence)
Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]

Cf. A284116, A284119, A284121, A291793.

Asveld's Table 1 gives data about the behavior of Post's 3-shift tag system {00/1101} applied to the word (100)^n. The first column gives n, the nonzero values in column 2 give A291792, and columns 3 through 7 give A284119, A291793 (or A284121), A291794, A291795, A291796. For the corresponding data for Watanabe's 3-shift tag system {00/1011} applied to (100)^n see A292089, A292090, A292091, A292092, A292093, A292094.

a(8)-a(17) from Lars Blomberg, Sep 08 2017

a(18)-a(55) from Lars Blomberg, Oct 15 2017

A230627 Prime reached in A230626, or -1 if no prime is reached.

Original entry on oeis.org

2, 3, 31, 5, 11, 7, 11, 23, 31, 11, 43, 13, 23, 29, 251, 17, 23, 19, 251, 31, 43, 23, 47, 43, 463, 29, 23, 29, 127, 31, 31, 59, 23, 47, 8093, 37, 83, 61, 127, 41, 179, 43, 467, 463, 23, 47, 83, 127, 467, 113, 173, 53, 47, 23, 179, 241, 127, 59, 349, 61, 179

Offset: 2

N. J. A. Sloane, Oct 27 2013

David J. Seal found that the number 255987 is fixed by the map described in A230625 (or equally A287874), so a(255987) = -1. - N. J. A. Sloane, Jun 15 2017
I also observe that the numbers 1007 and 1269 are mapped to each other by that map, as are the numbers 1503 and 3751 (see the b-file submitted by Chai Wah Wu for A230625). So a(1007) = a(1269) = a(1503) = a(3751) = -1. - David J. Seal, Jun 16 2017
a(217) = a(255) = a(446) = a(558) = a(717) = a(735) = a(775) = a(945) = a(958) = -1 since the trajectory either converges to (1007,1269) or to (1503,3751). - Chai Wah Wu, Jun 16 2017
See A287878 for the trajectory of 234. - N. J. A. Sloane, Jun 17 2017
See A288894 for the trajectory of 3932. - Sean A. Irvine, Jun 18 2017
The latest information seems to be that for numbers less than 12388, all trajectories either end at a fixed point or in a cycle of length 2. - N. J. A. Sloane, Jul 27 2017

Sean A. Irvine, Table of n, a(n) for n = 2..10000 (terms 2..3931 from Chai Wah Wu)
N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Base-2 analog to A195264.
Cf. A230625, A230626, A287878.
See A287875 for these same numbers written in binary.
See A288847 for where the values -1 occur.

fn[n_] := FromDigits[Flatten[IntegerDigits[ReplaceAll[FactorInteger[n], {x_, 1} -> {x}], 2]], 2];
Table[NestWhile[fn, n, # != 1 && ! PrimeQ[#] &], {n, 2, 50}] (* Robert Price, Mar 16 2020 *)

More terms from Chai Wah Wu, Jul 15 2014

Changed the "escape" value from 0 to -1 to be consistent with A195264. - N. J. A. Sloane, Jul 27 2017

A291790 Numbers whose trajectory under iteration of the map k -> (sigma(k)+phi(k))/2 consists only of integers and is unbounded.

Original entry on oeis.org

270, 290, 308, 326, 327, 328, 352, 369, 393, 394, 395, 396, 410, 440, 458, 459, 465, 496, 504, 510, 525, 559, 560, 570, 606, 616, 620, 685, 686, 702, 712, 725, 734, 735, 737, 738, 745, 746, 747, 783, 791, 792, 805, 806, 813, 814, 815, 816, 828

Offset: 1

N. J. A. Sloane, Sep 03 2017

nonn

It would be nice to have a proof that these trajectories are integral and unbounded, or, of course, that they eventually reach a fractional value (and die), or reach a prime (which is then a fixed point). (Cf. A291787.) If either of the last two things happen, then that value of n will be removed from the sequence. AT PRESENT ALL TERMS ARE CONJECTURAL.

When this sequence was submitted, there was a hope that it would be possible to prove that these trajectories were indeed integral and unbounded. This has not yet happened, although see the remarks of Andrew R. Booker in A292108. - N. J. A. Sloane, Sep 25 2017

Hugo Pfoertner, Table of n, a(n) for n = 1..82
Sean A. Irvine, Showing how the initial portions of some of these trajectories merge
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A000010, A000203, A289997, A290001, A291789 (the trajectory of 270), A291787, A292108.

For the "seeds" see A292766.

More terms from Hugo Pfoertner, Sep 03 2017

A359252 Number of vertices among all distinct circles that can be constructed from n equally spaced points along a line using only a compass.

Original entry on oeis.org

2, 13, 46, 101, 226, 417, 744, 1169, 1802, 2599, 3742, 5139, 7022, 9261, 12110, 15367, 19456, 24117, 29858, 36323, 43950, 52595, 62784, 73931, 86806, 101059, 117364, 135155, 155506

Offset: 2

Scott R. Shannon, Dec 22 2022

A circle is constructed for every pair of the n points, the first point defines the circle's center while the second the radius distance. The number of distinct circles constructed for n points is A001859(n-1).

No formula for a(n) is currently known.

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 10.
Scott R. Shannon, Image for n = 11.
Scott R. Shannon, Image for n = 20.

Cf. A359253 (regions), A359254 (edges), A359258 (k-gons), A001859, A290447, A331702, A358746.

a(n) = A359254(n) - A359253(n) + 1 by Euler's formula.

A290001 Numbers k such that the iteration k -> (sigma(k)+phi(k))/2 terminates at a fraction later than at the first step.

Original entry on oeis.org

12, 14, 15, 20, 24, 28, 33, 34, 35, 42, 48, 54, 55, 56, 62, 63, 69, 70, 76, 77, 78, 84, 85, 86, 87, 88, 90, 93, 94, 95, 96, 99, 102, 104, 105, 108, 110, 111, 112, 118, 119, 120, 122, 123, 124, 125, 129, 130, 132, 141, 142, 143, 148, 150

Offset: 1

Hugo Pfoertner, Sep 03 2017

nonn

Termination at the first step occurs if k>3 is a square or twice a square, i.e. if k is a term of A028982. So the sequence lists the numbers that end at a fraction but are not of one of these two forms.

			42 is in the sequence because the following iteration reaches an odd sigma(k):
   k        sigma(k)     phi(k)
   42          96          12  k->(sigma(k)+phi(k))/2, (96+12)/2=54
   54         120          18  k->(sigma(k)+phi(k))/2, (120+18)/2=69
   69          96          44  ...
   70         144          24  ...
   84         224          24
  124         224          60
  142         216          70
  143         168         120  k->(sigma(k)+phi(k))/2, (168+120)/2=144
  144         403          48  sigma(144) is odd, iteration terminates

Hugo Pfoertner, Table of n, a(n) for n = 1..101
Hugo Pfoertner, Table of n, a(n) for n = 1..1136 (values above first 101 terms are only guesses)
N. J. A. Sloane, Iterating some number-theoretic functions, Posting to Seqfan mailing list, Sep 3, 2017
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A000010, A000203, A028982, A289997, A291790, A291791.

b-file curtailed beyond last certain value, moved other values to a-file. - N. J. A. Sloane, Oct 01 2017

A291787 Trajectory of 45 under repeated application of the map k -> A291784(k).

Original entry on oeis.org

45, 48, 56, 60, 80, 88, 92, 94, 95, 96, 112, 120, 160, 176, 184, 188, 190, 216, 252, 324, 378, 486, 567, 594, 738, 876, 1032, 1224, 1488, 1776, 2112, 2624, 2656, 2672, 2680, 2976, 3552, 4224, 5248, 5312, 5344, 5360, 5952, 7104, 8448, 10496, 10624

Offset: 0

N. J. A. Sloane, Sep 02 2017

nonn

It may be that every trajectory under iteration of the map k -> A291784(k) which increases indefinitely will eventually merge with this sequence. This is certainly true for the terms 45 through 152 of A291788. - N. J. A. Sloane, Sep 24 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
C. R. Wall, Unbounded sequences of Euler-Dedekind means, Amer. Math. Monthly, 92 (1985), 587.

Cf. A000010, A001615, A291784, A291785, A291786, A291788.

a(n) = 2*a(n-7) for n >= 35, which proves this is unbounded. [Guy, Wall]

More terms from Hugo Pfoertner, Sep 03 2017

A291789 Trajectory of 270 under repeated application of k -> (phi(k)+sigma(k))/2.

Original entry on oeis.org

270, 396, 606, 712, 851, 852, 1148, 1416, 2032, 2488, 2960, 4110, 5512, 6918, 8076, 10780, 16044, 23784, 33720, 55240, 73230, 97672, 118470, 169840, 247224, 350260, 442848, 728448, 1213440, 2124864, 4080384, 8159616, 13515078, 15767596, 18626016, 29239504, 39012864, 62623600, 92580308

Offset: 0

N. J. A. Sloane, Sep 03 2017

nonn

The ultimate fate of this trajectory is presently unknown. It may reach a fractional value (when it dies), it may reach a prime (which would be a fixed point), it may enter a cycle of length greater than 1, or it may be unbounded. - Hugo Pfoertner and N. J. A. Sloane, Sep 18 2017

Sean A. Irvine, Table of n, a(n) for n = 0..515 [Terms through a(250) from Hugo Pfoertner, terms a(251)-a(356) from N. J. A. Sloane]
Sean A. Irvine, Illustration of A291789 showing a(n+1)/a(n) (red), cumulative mean of a(n+1)/a(n) (green), and power of 2 in a(n) (blue)
Hugo Pfoertner, Illustration of A291789 using a recursive 5th order Butterworth filter with normalized cut-off frequency of 0.1 (0.5<->Nyquist frequency) to smooth the data.
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.

Cf. A000010, A000203, A289997, A290001, A291790, A291787, A291804, A291805.

See A291914 and A292108 for the "big picture".

orbit:= proc(n, m) uses numtheory;
  local V,k;
  V:= Vector(m);
  V[1]:= n;
  for k from 2 to m do V[k]:= (sigma(V[k-1])+ phi(V[k-1]))/2 od:
  convert(V,list)
end proc:
orbit(270, 200); # Robert Israel, Sep 07 2017

NestWhileList[If[! IntegerQ@ #, -1/2, (DivisorSigma[1, #] + EulerPhi@ #)/2] &, 270, Nor[! IntegerQ@ #, SameQ@ ##] &, 2, 38] (* Michael De Vlieger, Sep 19 2017 *)

A292108 Iterate the map k -> (sigma(k) + phi(k))/2 starting at n; a(n) is the number of steps to reach either a fixed point or a fraction, or a(n) = -1 if neither of these two events occurs.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 3, 2, 1, 0, 1, 0, 2, 2, 1, 0, 4, 1, 2, 1, 4, 0, 2, 0, 1, 4, 3, 2, 1, 0, 3, 2, 1, 0, 9, 0, 2, 3, 1, 0, 7, 1, 1, 2, 1, 0, 8, 3, 2, 2, 1, 0, 3, 0, 8, 7, 1, 3, 2, 0, 1, 7, 6, 0, 1, 0, 3, 2, 4

Offset: 1

Hugo Pfoertner and N. J. A. Sloane, Sep 18 2017

nonn

The first unknown value is a(270).
For an alternative version of this sequence, see A291914.
From Andrew R. Booker, Sep 19 2017 and Oct 03 2017: (Start)
Let f(n) = (sigma(n) + phi(n))/2. Then f(n) >= n, so the trajectory of n under f either terminates with a half-integer, reaches a fixed point, or increases monotonically. The fixed points of f are 1 and the prime numbers, and f(n) is fractional iff n>2 is a square or twice a square.
It seems likely that a(n) = -1 for all but o(x) numbers n <= x. See link for details of the argument. (End)

			Let f(k) = (sigma(k) + phi(k))/2. Under the action of f:
14 -> 15 -> 16 -> 39/2, taking 3 steps, so a(14) = 3.
21 -> 22 -> 23, a prime, in 2 steps, so a(21) = 2.

Hugo Pfoertner, Table of n, a(n) for n = 1..269
Andrew R. Booker, Notes on (sigma + phi)/2
Sean A. Irvine, Showing how the initial portions of some of these trajectories merge
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.

Cf. A000010, A000203, A289997, A290001, A291790, A291787, A291804, A291805, A291914.

With[{i = 200}, Table[-1 + Length@ NestWhileList[If[! IntegerQ@ #, -1/2, (DivisorSigma[1, #] + EulerPhi@ #)/2] &, n, Nor[! IntegerQ@ #, SameQ@ ##] &, 2, i, -1] /. k_ /; k >= i - 1 -> -1, {n, 76}]] (* Michael De Vlieger, Sep 19 2017 *)

a(n) = 0 if n is 1 or a prime (these are fixed points).

a(n) = 1 if n>2 is a square or twice a square, since these reach a fraction in one step.

cp's OEIS Frontend

A039655 Number of iterations of f(x) = sigma(x)-1 applied to n required to reach a prime, or -1 if no prime is ever reached.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A292105 Irregular triangle read by rows: T(n,k) = the number of interior points that are the intersections of exactly k chords in the configuration A006561(n) (n >= 1, k >= 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A291792 Numbers m such that Post's tag system started at the word (100)^m eventually dies (i.e., reaches the empty string).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A230627 Prime reached in A230626, or -1 if no prime is reached.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A291790 Numbers whose trajectory under iteration of the map k -> (sigma(k)+phi(k))/2 consists only of integers and is unbounded.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A359252 Number of vertices among all distinct circles that can be constructed from n equally spaced points along a line using only a compass.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A290001 Numbers k such that the iteration k -> (sigma(k)+phi(k))/2 terminates at a fraction later than at the first step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A291787 Trajectory of 45 under repeated application of the map k -> A291784(k).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A291789 Trajectory of 270 under repeated application of k -> (phi(k)+sigma(k))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs