pad

PAD Sequence Subsystem

This document explains in detail how the PAD sequence generation subsystem works.

Overview

The sequence subsystem generates mathematical sequences like prime numbers, Fibonacci numbers, triangular numbers, and many more. It supports 122 different sequence types, filtering, transformations, and various output actions.

Entry Point

A sequence tag enters through sequence/tag.php:

include PQ . 'inits/tag.php';        // The tag's name, parameters and options
include PQ . 'inits/inits.php';      // Variables, plays, actions, limits
include PQ . 'build/build.php';      // Generate the sequence
include PQ . 'exits/exits.php';      // Post-actions, storing, info

return include PQ . 'exits/return.php';   // The rows for the tag

The expression form sequence:<type>(n) enters through sequence/sequence.php, which runs the same build for one term (inits/direct.php, inits/eval.php, build/inits.php, inits/init.php, …, build/build.php, exits/actions.php) and returns the term at that position, not a list - sequence:fibonacci(8) is 13. A type with a function.php answers the position from its formula, without a walk; any other walks from its first term, and the terms a lookup made are kept for the request (pqTermsMade), so a later lookup at or below them is answered from them. A position the type does not reach within the limits below is '', and under the strict check an error that names the limit.

Constants

The subsystem uses two path constants:

Parameters

Parameters control how sequences are generated (inits/parms.php):

Parameter Default Description
from 1 Where the loop starts - a value for the types that test candidates, a position for the ones that compute the nth term
to PHP_INT_MAX Where the loop ends, counting the same way as from
sole none Generate single value (sets from=to)
minimal PHP_INT_MIN Minimum acceptable value
maximal PHP_INT_MAX Maximum acceptable value
increment 1 Step between iterations, 1 or more - a range ('0..1') also counts in a step below 1
rows varies Maximum number of results
try varies Maximum iterations to attempt
stop PHP_INT_MAX Stop when value reaches this
skip 0 Skip the first N candidates offered - not the first N kept, so on a filtered sequence it drops fewer terms than N
randomly ’’ Enable random selection
unique ’’ Only unique values
name ’’ Name for storing sequence
build ’’ Override build type
toData ’’ Store to data
negative 0 Invert an action’s selection; has no effect on a play, which inverts by using remove instead of keep
pull ’’ Pull from stored sequence
push ’’ Push to stored sequence

Limits

Four settings in pad/config/sequence.php bound a run:

Setting Default What it bounds
$padSeqDefaultRows 10 The terms a tag makes when it names no rows= and has no end of its own
$padSeqDefaultTries 10,000 The candidates a filtered sequence tests when it names no try= - and how many terms membership (keep, remove, flag) makes of a type it has to look in
$padSeqMaxTries 1,000,000 The ceiling of candidates: try=, stop=, to= and a position lookup go no further
$padSeqMaxSeconds 5 The time a run walks its candidates

The time is looked at between candidates. One candidate - a costly test, a formula at a far position - and an action over the finished list are not cut off while they run, so it is no deadline for the request; PHP’s max_execution_time is.

A run that ran out of candidates or time answers the terms it found, as one that came to its end does: {sequence prime, rows=10, try=5} gives the three primes up to 5, and count after it says 3, with no mark that seven are missing. A position lookup does say so - under the strict check sequence:strong(5) is an error naming the limit it ran into.

A tag’s terms are made in full before its rows render - there is no lazy iteration; rows=, page= and the limits decide how many are made.

Build Types

The subsystem supports different build strategies (build/types/):

1. Loop Build (build/types/loop.php)

Iterates from $pqFrom to $pqTo, calling the sequence’s loop.php file for each value:

$pqGo   = $pqFrom;
$pqWalk = 'loop';
include PQ . 'build/one.php';   // the walk: $pqLoop = $pqGo, ..., $pqGo += $pqInc

2. Fixed Build (build/types/fixed.php)

Uses a pre-computed array from the sequence’s fixed.php file:

$pqFixed = include PT . "$pqSeq/fixed.php";
$pqWalk  = 'fixed';
include PQ . 'build/one.php';   // the walk: each entry, from/to selecting a slice of the list

3. Bool Build (build/types/bool.php)

Tests each number with a boolean function (e.g., pqBoolPrime()):

$pq = ( 'pqBool' . ucfirst($pqSeq) ) ( $pqLoop, $pqParm );

4. Function Build (build/types/function.php)

Calls a custom function:

$pq = ( 'pq' . ucfirst($pqSeq) ) ( $pqLoop );

5. Make Build (build/types/make.php)

Generates the next value from current loop value (e.g., even numbers):

$pq = include PT . "$pqSeq/make.php";

6. Order Build (build/types/order.php)

Generates values that depend on previous values (e.g., Fibonacci):

$pq = include PT . "$pqSeq/order.php";

7. Check Build (build/types/check.php)

Answers whether a value is a term of a type - the build of keep, remove and flag. The cheapest test the type has decides: its bool.php, the whole list its fixed.php or build.php returns, its precomputed table, and failing those the terms are made and looked in:

A term past the ceiling is no term of the run: {sequence list='9223372036854775806', flag, eval='@ * 2'} is 0, though @ * 2 makes it at position 4611686018427387903.

8. Pull Build (build/types/pull.php)

Retrieves a previously stored sequence.

Value Generation (build/one.php)

build/one.php is the walk itself, included once by the iterator: a loop over the candidates, each settled in a do { ... } while ( FALSE ) block - break goes on to the next candidate, break 2 ends the build. For each candidate:

$pqTries++;
if ( $pqTries > $pqTry ) break 2;  // Max attempts reached

// Generate value based on build type
if     ( pqStore($pqBuild) )    $pq = $pqLoop;
elseif ( $pqBuild == 'bool' )   $pq = pqBoolXxx($pqLoop, $pqParm);
elseif ( $pqBuild == 'function') $pq = pqXxx($pqLoop);
elseif ( $pqBuild == 'check' )  $pq = include PQ . "build/mode.php";
elseif ( $pqBuild == 'loop' )   $pq = include PT . "$pqSeq/loop.php";
elseif ( $pqBuild == 'make' )   $pq = include PT . "$pqSeq/make.php";
elseif ( $pqBuild == 'order' )  $pq = include PT . "$pqSeq/order.php";

// Apply filters (plays)
if ( count($pqPlays) ) {
  include PQ . 'plays/plays.php';
  if ( $pq === FALSE ) break;  // Filtered out, next candidate
}

// Apply constraints
if ( $pq < $pqMin ) break;                // Below minimum
if ( $pq > $pqMax ) break;                // Above maximum
if ( $pqUnique and isset ( $pqUniqueSeen [pqValueKey($pq)] ) ) break;  // Duplicate

// Add to result
$pqResult[] = $pq;

// Check stop conditions
if ( $pq >= $pqStop ) break 2;
if ( count($pqResult) >= $pqRows ) break 2;

It was a file the iterators included for every candidate, and an include costs what binding each variable the file names to the scope costs - some 320 ns a candidate for the 38 it names, most of what a candidate of a plain list took.

Sequence Types

The 122 sequence types are organized in types/ with this structure:

types/
├── prime/
│   ├── bool.php       # pqBoolPrime() - tests if n is prime
│   ├── function.php   # pqPrime() - generates primes
│   ├── generated.php  # PADprime constant with pre-computed values
│   ├── loop.php       # Returns next prime >= n
│   ├── make.php       # Finds next prime from n
│   └── flags/         # Type-specific flags
├── fibonacci/
│   ├── order.php      # The order build: the seeds 0 and 1, then go.php
│   ├── go.php         # The sum of the two terms before - shared with lucas
│   ├── generated.php  # PADfibonacci constant
│   └── flags/
├── triangular/
│   ├── bool.php       # Tests if n is triangular
│   ├── generated.php  # PADtriangular constant
│   └── flags/
...

Type File Purposes

File Purpose
bool.php Boolean test function pqBoolXxx($n)
function.php Generator function pqXxx($n)
generated.php Pre-computed constant array PADxxx
loop.php Value generator for loop build
make.php Value generator for make build
order.php Order-dependent generator (uses previous values)
go.php Alternative generator
init.php Type initialization
flags/ Type-specific configuration flags

Sequence Categories

Arithmetic Operations:

Bitwise Operations: (on the bits of the value, not on true and false)

Number Properties:

Figurate Numbers:

3D Figurate Numbers:

Famous Sequences:

Special:

Utility:

Rounding:

Plays (Filters)

Plays filter or transform values before adding to results (plays/plays.php):

foreach ( $pqPlays as $pqTmp ) {
  extract ( $pqTmp );
  $pqLoop = $pq;
  $pq = include PQ . "plays/play/$pqBuild.php";

  // Play modes:
  if ( $pqPlay == 'make' )   // Transform value
  if ( $pqPlay == 'keep' )   // Keep only matching
  if ( $pqPlay == 'remove' ) // Remove matching
  if ( $pqPlay == 'flag' )   // Return 1/0 flag
}

Play Modes:

Mode Returns TRUE Returns FALSE Returns other
make Use loop value Skip Use returned value
keep Keep value Skip Keep if matches loop
remove Skip Keep Skip if matches loop
flag Return 1 Return 0 1 if matches, 0 otherwise

Actions

Actions transform the final result array (actions/types/):

Aggregation

Selection

Modification

Ordering

Filtering

Set Operations

Random Support

The subsystem supports randomization at multiple levels:

Random Parameters

Parameters can include ranges with ..:

from='1..100'      # Random from 1-100
increment='1..5'   # Random increment 1-5
rows='5..10'       # Random 5-10 rows

Random Selection

With randomly option, values are selected randomly from the valid range instead of sequentially.

Random Increment

With increment='1...5' (three dots, quoted), the increment changes randomly each iteration. Unquoted, 1...5 is read as the number 1.5 and the step is that fraction.

Pre-computed Values

Many sequences include pre-computed constants in generated.php:

const PADfibonacci = [0,1,1,2,3,5,8,13,21,34,55,89,...];
const PADtriangular = [1,3,6,10,15,21,28,36,45,55,...];
const PADprime = [2,3,5,7,11,13,17,19,23,29,...];

These enable fast lookups for common sequences.

Directory Structure

sequence/
├── sequence/
│   ├── tag.php          # Entry point of a sequence tag
│   └── sequence.php     # Entry point of sequence:<type>(n)
│
├── inits/               # Initialization
│   ├── clear.php        # Clear state
│   ├── direct.php       # Direct entry setup
│   ├── limits.php       # Set iteration limits
│   ├── parms.php        # Parse parameters
│   ├── set.php          # Setup sequence type
│   └── vars.php         # Initialize variables
│
├── build/               # Sequence generation
│   ├── build.php        # Main build dispatcher
│   ├── check.php        # Check build type
│   ├── given.php        # Handle given build name
│   ├── include.php      # Include type files
│   ├── one.php          # Generate one value
│   ├── parm.php         # Parameter handling
│   ├── randomly/        # Random support
│   └── types/           # Build type handlers
│       ├── bool.php
│       ├── build.php
│       ├── check.php
│       ├── fixed.php
│       ├── function.php
│       ├── given.php
│       ├── loop.php
│       ├── make.php
│       ├── order.php
│       ├── pull.php
│       └── type/        # Type-specific handlers
│
├── plays/               # Filter system
│   ├── add.php          # Add play filter
│   ├── init.php         # Initialize plays
│   ├── inits.php        # Setup plays
│   ├── parm.php         # Play parameters
│   ├── plays.php        # Execute plays
│   └── play/            # Play type handlers
│
├── actions/             # Result transformations
│   ├── actions.php      # Execute actions
│   ├── assoc.php        # Associative handling
│   ├── function.php     # Function actions
│   ├── inits.php        # Setup actions
│   ├── merge.php        # Merge handling
│   ├── set.php          # Set actions
│   ├── double/          # Double-value actions
│   ├── merge/           # Merge actions
│   ├── negative/        # Negative handling
│   ├── order/           # Order actions
│   ├── parm/            # Parameterized actions
│   ├── single/          # Single-value actions
│   └── types/           # Action implementations
│
├── exits/               # Exit processing
│   ├── actions.php      # Final actions
│   ├── data.php         # Data storage
│   ├── done.php         # Mark done
│   ├── exit.php         # Exit handler
│   ├── exits.php        # Exit processing
│   ├── info.php         # Debug info
│   ├── return.php       # Return handling
│   ├── extra/           # Extra processing
│   ├── info/            # Info generation
│   ├── return/          # Return handlers
│   └── store/           # Store handlers
│
├── options/             # Option handlers
│   └── types/           # Option types
│
└── types/               # 122 sequence types
    ├── add/
    ├── and/
    ├── antiprime/
    ├── bell/
    ... (122 types total)

Example Usage

Simple Range

{sequence '1..10'}
→ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

First 10 Primes

{sequence prime, rows=10}
→ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Fibonacci until 100 is reached

{sequence fibonacci, stop=100}
→ [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

stop ends the run at the first term that reaches it - that term included.

Even Numbers with Sum

{sequence even, stop=20, sum}
→ [110]

For a type such as even, from and to count terms rather than name values: {sequence even, from=2, to=20, sum} sums the 2nd to 20th even numbers, 4 to 40, and gives [418]. stop always names a value.

Primes Filtered by Palindrome

{sequence prime, rows=20, keep, palindrome}
→ [2, 3, 5, 7, 11, 101, 131, 151, 181, 191...]

Random Selection

{sequence prime, rows=5, randomly}
→ [17, 3, 41, 7, 23] (random primes)

From PHP

pqArray ( 'even', '', 'rows=3' ) is [ 2, 4, 6 ]: the terms of a type as the values they are. The parameter is a value of the type - text in it is never template source - and the options are the run’s named limits, from, to, sole, minimal, maximal, min, max, increment, rows, try, stop, skip, randomly, unique and build, as an array ([ 'rows' => 3 ]) or written 'rows=3, to=50'. Plays and actions are the tag’s. An expression for eval handed in from PHP is refused, as one from a value is: it is the template’s own text.

Boolean Functions

Each sequence type can have a boolean test function:

function pqBoolPrime($n, $p=0) {
  if (gmp_prob_prime($n))
    return TRUE;
  else
    return FALSE;
}

function pqBoolEven($n, $p=0) {
  if ($n & 1)
    return FALSE;
  else
    return TRUE;
}

function pqBoolTriangular($num) {
  // 0 and k(k+1)/2 for a whole k: k is about the square root of 2n, and the whole numbers
  // next to it are tried exactly - solved as a quadratic in floating point, the neighbours
  // of a triangular number past 10^16 came out triangular too
  if ( ! pqBoolWhole ( $num ) or $num < 0 )
    return false;
  if ( $num == 0 )
    return true;
  $num  = (int) $num;
  $root = (int) sqrt ( 2 * (float) $num );
  for ( $k = max ( 1, $root - 1 ); $k <= $root + 1; $k++ )
    if ( ( ( $k % 2 ) ? $k * intdiv ( $k + 1, 2 ) : intdiv ( $k, 2 ) * ( $k + 1 ) ) == $num )
      return true;
  return false;
}

The functions in pad/sequence/types/<type>/bool.php are the ones that run.

State Variables

Key state variables during generation:

Variable Purpose
$pqResult Result array
$pqLoop Current loop value
$pqTries Number of attempts
$pqSeq Current sequence type
$pqBuild Current build type
$pqParm Current parameter
$pqOrder Order array (for dependent sequences)
$pqPlays Active plays (filters)
$pqActions Active actions
$pqFixed Fixed array (for fixed builds)
This site is open source. Improve this page.