mystery sequence (easy?)

Peter Pein petsie at
Fri Mar 16 18:24:47 CET 2007

N. J. A. Sloane schrieb:
> Dear Seqfans:
> Can anyone figure this out?
> %I A109636
> %S A109636 2,3,9,10,27,28,30,81,84,88,90,100,104,243,252,264,270,272,280,300,304,
> %T A109636 312,729,736,756,784,792,810,816,840,880,900,912,928,936,992,1000,1040,
> %U A109636 2187,2208,2268,2352,2368,2376
> %N A109636 Minimal numbers in k-almost prime numbers massiv of (n,k) such that number of (n,k+l) is equal 2^l times the number of (n,k) for any l>0.
> %H A109636 Wikipedia, <a href="">k-almost prime numbers</a>.
> %Y A109636 Cf. A000040, A001358, A014612, A014613, A014614.
> %Y A109636 Sequence in context: A047358 A003140 A057234 this_sequence A057236 A063257 A103039
> %Y A109636 Adjacent sequences: A109633 A109634 A109635 this_sequence A109637 A109638 A109639
> %K A109636 nonn,uned,obsc
> %O A109636 1,1
> %A A109636 Yury V. Shlapak (shlapak(AT), Aug 04 2005
> Possibly one of the Russian-speaking members of the list can
> help by translating it to Russian, where it might be clearer?
> What does "(n,k)" mean???
> Neil
> PS The "binary splitting" mystery sequence A126119 of the other day remains
> a mystery

If you wite the k-almost primes in rows (one row for each k), you'll observe
that there exist P_{k_0}(n) with P_{k_0+1}(n)=2P_{k_0}(n). For each k>=k0:
P_{k+1}(n)=2P_{k}(n). A109636 is the sequence of the P_{k0}(n). In other
words: In the columns the values double from row k0 on.

Well, english isn't my mother toungue too.

Mathematica-speaking members might be able to translate this to better english:

A109636list[n_] :=
  Module[{p  = Prime[Range[n]], pal},
   pal = Transpose /@ Partition[
    NestList[Take[Union[Flatten[Outer[Times, #1, p]]], Length[#1]] & , p, n],
   2, 1]},
   Complement @@ Transpose[Cases[pal, {k_, kk_} /; kk == 2*k, {2}]]]

 {2, 3, 9, 10, 27, 28, 30, 81, 84, 88, 90, 100, 104, 243, 252, 264, 270,
  272, 280, 300, 304, 312, 729, 736, 756, 784, 792, 810, 816, 840, 880, 900,
  912, 928, 936, 992, 1000, 1040, 2187, 2208, 2268, 2352, 2368, 2376, 2430,
  2448, 2464, 2520, 2624, 2640, 2700, 2720, 2736, 2752, 2784, 2800, 2808,
  2912, 2976, 3000, 3008, 3040, 3120, 6561, 6624, 6784, 6804, 7056, 7104,
  7128, 7290, 7344, 7360, 7392, 7552, 7560, 7616, 7744, 7808, 7840, 7872,
  7920, 8100, 8160, 8208, 8256, 8352, 8400, 8424, 8512, 8576, 8736, 8800,
  8928, 9000, 9024, 9088, 9120, 9152, 9280}


well, I guess I will leave it in the OEIS, now that both Alex and Peter
have worked on it!

Thanks for all your help!

I will revise the entry over the next few days


Dear Mathfun, Seqfans:

Numbers of set systems of various types

There are some sequences that may be missing from the OEIS,
in case somebody would be interested in calculating them.

This was suggested by reading pages 1 and 2 of the book by Heinz Koenig on
Measure and Integration (Springer, 1997)

We are considering a "set system" S,
which is a nonempty collection of subsets 
A of a set X, where X has n points.  There will be two
versions of each sequence, depending on whether the
points are labeled or unlabeled.

We define several properties which S might have:

U : A, B in S => A U B in S
I : A, B in S => A intersect B in S
\ : A, B in S with A contained in B => B\A in S
- : A in S => complement of A in X is in S
0 : S contains the empty set
1 : S contains the universe set X

We also define a new operation on subsets of X:

[points in P but not in A plus points in both Q and A]

Now Koenig defines 4 types of set systems:

a lattice   : properties U, I
an oval     : P,A,Q in S => |P|A|Q| in S
a ring      : properies U, I, \
an algebra  : properties U, I, -

The question is, how many lattices, ovals, rings, and algebras
are there on n labeled/unlabeled points?

(In fact one might consider any of the 2^7 combinations
of the above 7 properies!)

There are of course many sequences like these in the OEIS already,
but usually there is no precise definition (this should be corrected!)

For example: posets: A000112 (unlabeled), A001035 (labeled)
Boolean lattices: A005493
Set systems of various types, studied recently by

%I A102895
%S A102895 2,2,8,90,4542,2747402,151930948472
%N A102895 Number of ACI algebras or semilattices on n generators, with no identity element.
%C A102895 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
%C A102895 Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain the empty set.

- this seems to count subsets with properties I, 0 in the labeled case

%I A102897
%S A102897 2,4,14,122,4960,2771104,151947502948
%N A102897 Number of ACI algebras (or semilattices) on n generators.
%C A102897 Also counts Horn functions on n variables, boolean functions whose set of truth assignments are closed under 'and', or equivalently, the boolean functions that can be written as a conjunction of Horn clauses, clauses with at most one negative literal.
%C A102897 Also, number of families of subsets of {1,...,n} that are closed under intersection (because we can throw in the universe, or take it out, without affecting anything else).
%C A102897 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
- this seems to count subsets with property I in the labeled case ?

Likewise A102896 seems to count subsets with properties I, 1 in the labeled case
and      A102894 seems to count subsets with properties I, 0, 1 in the labeled case

(see the full entries for more details)


More information about the SeqFan mailing list