A187771 -id:A187771 - cp's OEIS frontend

A187824 a(n) is the largest m such that n is congruent to -1, 0 or 1 mod k for all k from 1 to m.

3, 4, 5, 6, 3, 4, 4, 5, 3, 6, 4, 4, 3, 5, 5, 4, 3, 6, 5, 5, 3, 4, 6, 6, 3, 4, 4, 7, 3, 6, 4, 4, 3, 7, 7, 4, 3, 5, 5, 8, 3, 4, 5, 5, 3, 4, 4, 8, 3, 5, 4, 4, 3, 9, 5, 4, 3, 6, 6, 6, 3, 4, 5, 6, 3, 4, 4, 5, 3, 10, 4, 4, 3, 5, 5, 4, 3, 6, 5, 5, 3, 4, 7, 7, 3, 4, 4, 6, 3, 7, 4, 4, 3, 6, 6, 4, 3, 5, 5, 6, 3

Offset: 2

Kival Ngaokrajang, Dec 27 2012

This sequence and A187771 and A187761 are winners in the contest held at the 2013 AMS/MAA Joint Mathematics Meetings. - T. D. Noe, Jan 14 2013
If n = t!-1 then a(n) >= t, so sequence is unbounded. - N. J. A. Sloane, Dec 30 2012
First occurrence of k = 3, 4, 5, ...:  2, 3, 4, 5, 29, 41, 55, 71, 881, 791, 9360, 10009, 1079, 30239, (17 unknown), 246960, (19 unknown), 636481, 1360800, 3160079, (23 unknown), 2162161, 266615999, 39412801 (27 unknown), 107881201, ... Searched up to 3*10^9. - Robert G. Wilson v, Dec 31 2012

			For n = 6, a(6) = 3 as follows.
m    Residue of 6 (mod m)
1             0
2             0
3             0
4             2
5             1
6             0
7            -1

N. J. A. Sloane, Table of n, a(n) for n = 2..10000
Don Reble, Division gets rough: OEIS A187824 and A220890

For values of n which set a new record see A220891.

For smallest inverse see A220890 and A056697.

A187824:= proc(n)
   local j,r;
   for j from 4 do
     r:= mods(n, j);
     if r <> r^3 then return j-1 end if
   end do
end proc; # Robert Israel, Dec 31 2012

f[n_] := Block[{k = 4, r}, While[r = Mod[n, k]; r < 2 || k - r < 2, k++]; k - 1]; Array[f, 101, 2] (* Robert G. Wilson v, Dec 31 2012 *)

A187824(n)={n++>2 && for(k=4,oo, n%k>2 && return(k-1))} \\ M. F. Hasler, Dec 31 2012, minor edits Aug 20 2020

a(n)=my(k=3);n++;while(n%k++<3,);k-1 \\ Charles R Greathouse IV, Jan 02 2013

from gmpy2 import t_mod
def A187824(n):
    k = 1
    while t_mod(n+1,k) < 3:
        k += 1
    return k-1 # Chai Wah Wu, Aug 31 2014

def a(n):
   m=1
   while abs(n%m) < 2:
      m += 1
   return m
[a(n) for n in range(1,100)]
# Derek Orr, Aug 31 2014, corrected & edited by M. F. Hasler, Aug 20 2020

If n == 0 (mod 20), then a(n-2) = a(n+2) = 3, while a(n) = 5,5,6, 5,5,8, 5,5,6, 5,5,6, 5,5,7, 5,5,6, 5,5,7, ... with records a(20) = 5, a(60) = 6, a(120) = 8, a(720) = 10, a(2520) = 12, a(9360) = 13, ... If n == 0 (mod 5), but is not a multiple of 20, then always a(n-2) = a(n+2) = 4, while a(n) = 6,3,5, 6,3,7, 5,3,9, 6,3,5, 7,3,6, 5,3,6, 7,3,5, ... - Vladimir Shevelev, Dec 31 2012

a(n)=3 iff n == 2 (mod 4). a(n)=4 iff n == 3, 7, 8, 12, 13, 17 (mod 20), i.e., n == 2 or 3 (mod 5) but not n == 2 (mod 4). In the same way one can obtain a covering set for any value taken by a(n), this is actually nothing else than the definition. For example, n == 2, 3 or 4 (mod 6) but not 2 or 3 (mod 5) nor 2 (mod 4) yields a(n)=5 iff n == 4, 9, 15, 16, 20, 21, 39, 40, 44, 45, 51 or 56 (mod 60), etc. - M. F. Hasler, Dec 31 2012

Corrected m = 100 by Kival Ngaokrajang, Dec 30 2012
Definition & example corrected by Kival Ngaokrajang, Dec 30 2012
More terms from N. J. A. Sloane, Dec 30 2012

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Original entry on oeis.org

1, 1, 2, 6, 23, 106, 568, 3459, 23544, 176850, 1451253, 12904312, 123489888, 1264591561, 13790277294, 159466823794, 1948259002647, 25066729706582, 338670605492700, 4792623436607059, 70873649458154500, 1092969062435462254, 17543703470388927229, 292600906102204630092

Offset: 0

Joerg Arndt, Jan 04 2013

This sequence and A187771 and A187824 are winners in the contest held at the 2013 AMS/MAA Joint Mathematics Meetings. - T. D. Noe, Jan 14 2013
Number of monotonic-labeled forests on n vertices with rooted trees of height less than 3. A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex. (See comment by Dennis P. Walsh at A000110; with "greater" instead of "smaller".) To see this, consider the maps [1,2,...,n] -> [0,1,...,n-1] with f(x) < x.
As the maps are valid (left) inversion tables for permutations (see example), we obtain a simple bijection between permutations and such forests.
For n>=3 column 3 of A179455; maps such that f^[k](x) = f^[k-1](x) correspond to column k of A179455 (for n>=k).
Explanation of the Maple routine by Alois P. Heinz, Jan 15 2013: (Start)
b(n,x,y) is the number of forests consisting of trees we want to count, where n nodes are still to be inserted and x nodes at level 0 (the roots) and y nodes at level 1 are already present, plus perhaps some nodes at level 2 (whose number is not of interest).
If the next node is inserted at level 0 then n-1 remaining nodes are to be inserted (and level 0 has one more node: x+1).  There is only one possibility to do that.
If the next node is inserted at level 1 then again n-1 nodes are to be inserted (and level 1 has one more node: y+1).  The inserted node can have x different predecessors (at level 0), accounted by the multiplication by x.
If a node is inserted at level 2 then (again) n-1 nodes are to be inserted and level 2 has one more node (which is not counted).  The inserted node can have y predecessors, accounted by the multiplication by y.
b(0,x,y) = 1 counts any fixed forest that has received all its nodes.
b(n,0,0) counts all forests that can be constructed by inserting n nodes into the empty forest.
(End)
Also the row sums of the Bell transform of the Bell numbers. Since the Bell numbers are the row sums of the Bell transform of the Stirling_2 numbers they might also be called second order Bell numbers. (Also note that the Stirling_2 numbers are the row sums of the Bell transform of the simplest sequence of positive numbers 1,1,1,... which in turn are the row sums of the Bell transform of the characteristic function of 0. See the link 'Bell Transform' for more about this hierarchy which might be called the Bell hierarchy.) - Peter Luschny, Jan 23 2016

			There are a(4)=23 such maps f: [0,1,2,3] -> [0,1,2,3], all 4-digit mixed-radix numbers [f(0), f(1), f(2), f(3)] where 0 <= f(k) <= k (rising factorial basis) except for [ 0 0 1 2 ], as f(3)=2 and f(f(3)) = f(2) = 1 != f(f(f(3))) = f(f(2)) = f(1) = 0.
The exception corresponds to the tree 0 -- 1 -- 2 -- 3 (0 is the root), which can be identified with the map [1,2,3,4] -> [0,1,2,3] where f(k)=k-1.

Alois P. Heinz, Table of n, a(n) for n = 0..493
Peter Luschny, The Bell transform
Peter Luschny, Permutation Trees
D. P. Walsh, Counting forests with Stirling and Bell numbers

Cf. A000110 (Number of maps f: [n] -> [n] where f(x)<=x and f(f(x))=f(x) ).
Cf. A179455 (permutation trees of power n and height <= k+1 ).
Cf. A000949 (maps f: [n] -> [n] where f(f(x)) = f(f(f(x))) ).

b:= proc(n, x, y) option remember; `if`(n=0, 1,
       b(n-1, x+1, y) +x*b(n-1, x, y+1) +y*b(n-1, x, y))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 09 2013
# The function BellMatrix is defined in A264428.
B := BellMatrix(n -> combinat:-bell(n), 24):
seq(add(i, i=LinearAlgebra:-Row(B,n)), n=1..24); # Peter Luschny, Jan 23 2016
# alternative Maple program:
b:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*b(j-1, h-1)*b(n-j, h), j=1..n))
    end:
a:= n-> b(n, 2):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 21 2017

b[n_, x_, y_] := b[n, x, y] = If[n == 0, 1, b[n-1, x+1, y]+x*b[n-1, x, y+1]+y*b[n-1, x, y]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
Table[Sum[BellY[n, k, BellB[Range[n] - 1]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

/* using e.g.f. A(x) */
x = 'x + O('x^66);
B = exp( exp(x) - 1 );  /* e.g.f. of Bell numbers */
A = serconvol( x * B, -log(1-x) );
/* A = intformal(B) */ /* alternative to last line */
A = exp( A );
Vec( serlaplace( A ) )

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def a(n): return b(n, 2)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 21 2017, after second Maple program by Alois P. Heinz

Conjecture (confirmed below) about the e.g.f. A(x): Let B(x) = Sum_{n>=0} b(n) * x^n/n! = exp(exp(x)-1) the e.g.f. of the Bell numbers (A000110). Then A(x) = Sum_{n>=0} a(n) * x^n/n! = exp( Sum_{n>=0} b(n) * x^(n+1)/(n+1)! ), see PARI program.
From Joerg Arndt, Jan 14 2013: (Start)
Conjecture (confirmed below):  Let C(0,x) = 1 and for k>=1 C(k, x) = exp( integral(C(k-1,x)) ) then C(k,x) is the e.g.f. for monotonic-labeled forests on n vertices with rooted trees of height less than k (column k of A179455(n,k) for k>=1, n>=k).
For k=1 (C(1,x)=exp(x)) and k=2 (C(2,x)=exp(exp(x)-1)) this is known to be true, for k=3 this is the conjecture above. (End)
From Joerg Arndt, Jan 15 2013: (Start)
Gareth McCaughan, on the math-fun mailing list (Jan 14 2013), writes
"If F is the e.g.f. for Things Of Size n, then exp(F) is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.)
"Which means the conjecture is right. (The integral turns that into 'multisets of things whose sizes plus 1 add up to n'; a tree is a forest together with a new node on top.)"
(End)

cp's OEIS Frontend

A187824 a(n) is the largest m such that n is congruent to -1, 0 or 1 mod k for all k from 1 to m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A221262 Numbers k such that sigma(k) is the fourth power of the sum of the prime divisors of k.

Views

Author

Keywords

Examples

Links

Crossrefs

A221263 Numbers k such that sigma(k) is the fifth power of the sum of the prime divisors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs