A248218 -id:A248218 - cp's OEIS frontend

A247981 Primes dividing nonzero terms in A003095: the iterates of x^2 + 1 starting at 0.

2, 5, 13, 41, 137, 149, 229, 293, 397, 509, 661, 677, 709, 761, 809, 877, 881, 1217, 1249, 1277, 1601, 2053, 2633, 3637, 3701, 4481, 4729, 5101, 5449, 5749, 5861, 7121, 7237, 7517, 8009, 8089, 8117, 8377, 9661, 14869, 14897, 18229, 19609, 20369, 20441, 21493, 22349, 23917, 24781, 24977, 25717

Offset: 1

Charles R Greathouse IV, Sep 28 2014

nonn

Relative density in the primes is 0, see Jones theorem 5.5.

			2 and 13 are in the sequence since A003095(4) = 26. 3 is not in the sequence since it does not divide any member of A003095.

Charles R Greathouse IV, Table of n, a(n) for n = 1..500
Rafe Jones, The density of prime divisors in the arithmetic dynamics of quadratic polynomials, J. Lond. Math. Soc. (2) 78 (2) (2008), pp. 523-544.

Cf. A003095, A248218, A248219.

Select[Table[d=0; t=0; Do[t=Mod[t^2+1,Prime[j]]; If[t==0,d=1],{k,1,Prime[j]}]; If[d==1,Prime[j],0],{j,1,1000}],#!=0&] (* Vaclav Kotesovec, Oct 04 2014 *)

is(p)=my(v=List([1]),t=1); while(t,t=(t^2+1)%p; for(i=1,#v, if(v[i]==t, return(0))); listput(v,t)); isprime(p)

a(n) << exp(k^n) for some constant k > 0, see Jones theorem 6.1. In particular this sequence is infinite. - Charles R Greathouse IV, Sep 28 2014

A328700 Numbers k dividing nonzero terms in A003095.

Original entry on oeis.org

1, 2, 5, 10, 13, 26, 41, 65, 82, 130, 137, 149, 205, 229, 274, 293, 298, 397, 410, 458, 509, 533, 586, 661, 677, 685, 709, 745, 761, 794, 809, 877, 881, 1018, 1066, 1145, 1217, 1249, 1277, 1322, 1354, 1370, 1418, 1465, 1490, 1522, 1601, 1618, 1754, 1762, 1781, 1937, 1985, 2053, 2290

Offset: 1

Jianing Song, Oct 26 2019

nonn

k is a term if and only if A328699(k) = 0, in which case all the indices m such that k divides A003095(m) are m = t*A248218(k), t = 0, 1, 2, 3, ...

			41 divides A003095(7) = 210066388901, so 41 is in this sequence. In addition, 41 divides A003095(m) if and only if 7 divides m.
29 is not a term: {A003095(n) mod 29} = {0, 1, 2, 5, 26, 10, 14, 23, 8, 7, 21, 7, 21, 7, 21, ...}, so 29 does not divides A003095(m) for any m > 0.

Amiram Eldar, Table of n, a(n) for n = 1..1000

Cf. A003095, A328699, A248218.

The primes in this sequence are given by A247981.

v(n) = my(v=[0],k,flag=1); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, flag=0)); if(flag==0, break())); v;
is(n) = !(v(n)[#v(n)]);

A332966 a(n) is the largest value in the sequence s defined by s(1) = 0 and for any k > 0, s(k+1) = (s(k)^2+1) mod n.

Original entry on oeis.org

0, 1, 2, 2, 2, 5, 5, 5, 8, 7, 6, 5, 5, 12, 11, 10, 16, 17, 12, 17, 5, 17, 13, 5, 5, 5, 26, 26, 26, 26, 26, 26, 26, 33, 26, 29, 26, 31, 26, 37, 32, 26, 36, 26, 26, 33, 43, 26, 47, 30, 50, 26, 41, 53, 50, 26, 50, 50, 30, 50, 53, 57, 47, 37, 57, 26, 56, 65, 59

Offset: 1

Rémy Sigrist, Mar 04 2020

nonn

For any n > 0, the sequence s is eventually periodic, so this sequence is well defined.

a(n) tends to infinity as n tends to infinity.

			For n = 42:
- we have:
  k  s(k)
  -  ----
  1     1
  2     2
  3     5
  4    26
  5     5
  6    26
  ...
- the sequence s has largest value 26, so a(42) = 26.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Scatterplot of the first 750000 terms

Cf. A003095, A248218, A330405, A332965.

a(n) = { my (s=0, v=s, w=0); while (!bittest(w,s), w+=2^s; v=max(v,s); s=(s^2+1)%n); v }

a(n) >= A003095(k) for any k >=0 and n > A003095(k).

A248624 Hiccup sequence.

Original entry on oeis.org

4, 5, 4, 6, 4, 5, 7, 11, 10, 5, 6, 8, 10, 14, 11, 21, 14, 6, 7, 9, 21, 13, 15, 23, 14, 5, 20, 33, 41, 17, 7, 8, 10, 20, 35, 14, 14, 23, 16, 33, 31, 51, 20, 33, 13, 32, 50, 45, 53, 24, 44, 8, 9, 11, 17, 33, 35, 12, 4, 35, 40, 17, 47, 48, 31, 14, 25, 20, 40, 27

Offset: 2

Mason Bogue, Oct 10 2014

nonn

The hiccup sequence #n: Consider the sequences created by a_n = a[n-1] + a_[n-2] in Z mod n, with a certain "carrying" rule, where when the numbers a_[n-2] and a_[n-1] are added together in Z and the result is greater than n, two numbers are added to the sequence, first 1, and then a_[n-2] + a_[n-1] mod n. These sequences all fall into cycles of a different length:
2: 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0... [4]
3: 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 0, 1... [5]
4: 0, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3... [4]
5: 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3... [6]
6: 0, 1, 1, 2, 3, 5, 1, 2, 3, 5, 1, 2, 3, 5, 1, 2, 3... [4]
7: 0, 1, 1, 2, 3, 5, 1, 1, 2, 3, 5, 1, 1, 2, 3, 5, 1... [5]
8: 0, 1, 1, 2, 3, 5, 1, 0, 1, 1, 2, 3, 5, 1, 0, 1, 1... [7]
...and so on! It is easy to calculate and it seems to go on forever. But I do not have a proof.
Proof: This sequence continues forever. This is because the state of the sequence is totally determined by the previous two numbers, and it has only a finite number of states. Therefore, the same state of any carrying Fibonacci sequence must repeat after a finite period of time; in physics, this is Poincaré's recurrence theorem.
Proof: This sequence increases without bound. This is because in order to cycle a carrying Fibonacci sequence must wrap around at least once. Thus
  #_n ≥ sup{k in N, Fib[k] < n}

Lars Blomberg, Table of n, a(n) for n = 2..10000

Cf. A248218, A001175.

for i = 2, 100 do
  local a = {i}
  for j = 1, 20 do
      local k
      if j <3 then
         k = j-1
      else
         k = a[#a] + a[#a-1]
      end
      if k >= i then
         a[#a+1] = 1
         k = k - i
      end
      a[#a+1] = k
  end
    print(table.concat(a, ", "))
end

Corrected a(9) and added a(13)-a(71) by Lars Blomberg, Oct 18 2014

A328699 Start with 0, a(n) is the smallest number of iterations: x -> (x^2+1) mod n needed to run into a cycle.

Original entry on oeis.org

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

Offset: 1

Jianing Song, Oct 26 2019

nonn

Let f(0) = 0, f(k+1) = (f(k)^2+1) mod n, then a(n) is the smallest i such that f(i) = f(j) for some j > i.
Obviously a(n) <= A000224(n): f(1), f(2), ..., f(A000224(n)+1) are all of the form (s^2+1) mod n, so there must exists 0 <= i < j <= A000224(n)+1 such that f(i) = f(j), and a(n) <= i <= A000224(n). The equality seems to hold only for n = 3.
k divides A003095(m) for some m > 0 if and only if a(k) = 0, in which case all the indices m such that k divides A003095(m) are m = t*A248218(k), t = 0, 1, 2, 3, ...

			A003095(n) mod 3: 0, 1, (2). {A003095(n) mod 3} enters into the cycle (2) from the 2nd term on, so a(3) = 2.
A003095(n) mod 7: 0, 1, 2, (5). {A003095(n) mod 7} enters into the cycle (5) from the 3rd term on, so a(7) = 3.
A003095(n) mod 29: 0, 1, 2, 5, 26, 10, 14, 23, 8, (7, 21). {A003095(n) mod 29} enters into the cycle (7, 21) from the 9th term on, so a(29) = 9.
A003095(n) mod 37: 0, 1, 2, 5, 26, (11). {A003095(n) mod 37} enters into the cycle (11) from the 5th term on, so a(37) = 5.
A003095(n) mod 41: (0, 1, 2, 5, 26, 21, 32). {A003095(n) mod 41} enters into the cycle (0, 1, 2, 5, 26, 21, 32) from the very beginning, so a(41) = 0.

Cf. A003095, A248218 (cycle length), A328700, A000224.

a(n) = my(v=[0],k); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, return(j-1))))

cp's OEIS Frontend

A247981 Primes dividing nonzero terms in A003095: the iterates of x^2 + 1 starting at 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A328700 Numbers k dividing nonzero terms in A003095.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A332966 a(n) is the largest value in the sequence s defined by s(1) = 0 and for any k > 0, s(k+1) = (s(k)^2+1) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A248624 Hiccup sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Lua

Extensions

A328699 Start with 0, a(n) is the smallest number of iterations: x -> (x^2+1) mod n needed to run into a cycle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI