sidef/scripts/Extended tests/is_almost_prime.sf

#!/usr/bin/ruby

# Tests for the Number `is_almost_prime(n,k)` method.

# Timings:
#   17 feb 2023: 4.385s +/- 0.1
#   23 feb 2023: 3.913s
#   04 mar 2023: 3.635s
#   13 jul 2023: 3.364s
#   14 sep 2023: 2.575s (after removing a duplicated test)
#   23 sep 2023: 3.391s (after adding two more tests)
#   14 dec 2023: 3.894s (after adding more tests)

#~ Num!USE_CONJECTURES = true

define EXTRA = false     # true to run extra tests (slower)

func A242786(n) {
    for (var p = 2; true; p.next_prime!) {
        var v = (p**n + 1)
        v.is_almost_prime(n) || next
        return p
    }
}

assert_eq(
    A242786.map(1..11),
    %n[2, 3, 3, 43, 7, 41, 23, 643, 17, 557, 251],
)

assert_eq(A242786(21), 1151)

func A241793(n) {
    for k in (1..Inf) {
        var b = bigomega(k)*n
        var v = (k**n - 1)
        is_almost_prime(v, b) || next
        return k
    }
}

assert_eq(
    A241793.map(1..16),
    %n[3, 34, 5, 15, 17, 55, 79, 5, 53, 23, 337, 13, 601, 79, 241, 41],
)

assert_eq(A241793(24), 79)

func A368163(n) {
    for k in (1..Inf) {
        var v = (k**n - 1)
        is_almost_prime(v, n) || next
        return k
    }
}

assert_eq(
    A368163.map(1..16),
    %n[3, 4, 4, 10, 17, 8, 25, 5, 28, 9, 81, 13, 289, 64, 100, 41],
)

assert_eq(A368163(24), 79)
assert_eq(A368163(27), 961) if EXTRA
assert_eq(A368163(28), 729)
assert_eq(A368163(30), 361)

assert(is_almost_prime(961**27 - 1, 27))
assert(is_almost_prime(14015**26 - 1, 26)) if EXTRA
assert(is_almost_prime(2047**32 - 1, 32)) if EXTRA

func A368162(n) {
    for k in (1..Inf) {
        var v = (k**n + 1)
        is_almost_prime(v, n) || next
        return k
    }
}

assert_eq(
    A368162.map(1..15),
    %n[1, 3, 3, 43, 7, 32, 23, 643, 17, 207, 251, 3255, 255, 1568, 107],
)

assert_eq(A368162(21), 1151) if EXTRA
assert(is_almost_prime(1151**21 + 1, 21))
assert(is_almost_prime(4095**17 + 1, 17))
assert(is_almost_prime(6272**18 + 1, 18))

func A281940(n) {
    for k in (1..Inf) {
        var v = (k**n + 1)
        v.is_prob_squarefree(1e3) || next
        v.is_almost_prime(n) || next
        v.is_squarefree || next
        return k
    }
}

assert_eq(
    A281940.map(1..12),
    %n[1, 3, 9, 43, 46, 47, 245, 1697, 109, 565, 3938, 3255]
)

func A281940_alt(n) {
    for k in (1..Inf) {
        var v = (k**n + 1)
        v.is_squarefree_almost_prime(n) || next
        return k
    }
}

assert_eq(
    A281940_alt.map(1..12),
    %n[1, 3, 9, 43, 46, 47, 245, 1697, 109, 565, 3938, 3255]
)

func A280005(n) {
    for(var p = 2; true; p.next_prime!) {
        var v = (p**n + 1)
        v.is_prob_squarefree(1e3) || next
        v.is_almost_prime(n) || next
        v.is_squarefree || next
        return p
    }
}

assert_eq(
    A280005.map(1..10),
    %n[2, 3, 13, 43, 73, 47, 457, 1697, 109, 8161]
)

func A280005_alt(n) {
    for(var p = 2; true; p.next_prime!) {
        var v = (p**n + 1)
        v.is_squarefree_almost_prime(n) || next
        return p
    }
}

assert_eq(
    A280005_alt.map(1..10),
    %n[2, 3, 13, 43, 73, 47, 457, 1697, 109, 8161]
)

func A358863(n) {
    for k in (1..Inf) {
        var v = polygonal(k, n)
        if (v.is_almost_prime(n)) {
            return v
        }
    }
}

assert_eq(A358863.map(3..19), %n[28, 16, 176, 4950, 8910, 1408, 346500, 277992, 7542080, 326656, 544320, 120400000, 145213440, 48549888, 4733575168, 536813568, 2149576704])

func A358865(n) {
    for k in (1..Inf) {
        var v = pyramidal(k, n)
        if (v.is_almost_prime(n)) {
            return v
        }
    }
}

assert_eq(A358865.map(3..21), %n[20, 140, 405, 2856, 25296, 111720, 25984, 5474000, 237600, 223826688, 3852800, 268565760, 1834725376, 175861400000, 335674368, 2863363937280, 4383831556096, 206015846400, 3400704000])

assert(6378421230653912273852177516895163581869770560831402039659052275307515868158149242183187027058743269083585164524698761215608346720446543721867890772992768450030990772124462439643369906993789153742999577997533023369718005328697704646795653340413290216914429581800198907520670422145782789421503445838438309411889963011879677086315079680346076913198656865252722018507700079241053301126985375100206013999932788906892043402372100794021347723757962214999239405763985925478958053765385390392428991093620063803159748213554713516270836566432768442321417273611613661964043740485967874546203158330542419346172965725208847889307596664965692982489236584360678086793885224312622009679624680125435713130901431548084498643988804235541146098681538248403808764459574030837406569943265425119945515620987942036623366002995111745100363660322741847883390914005559246543930659653872917345326198079665168962285351976979752322993704768006328130917743545206406358713737580633683126888580933576598622705103763505867769189580877823254445988109717369710491787515696906699326587144119103036177901022625401163297714167068028230540962534246165735639040001.is_almost_prime(2))

assert(1536502117117468999680.is_almost_prime(28))
assert(21266854897681220860.is_almost_prime(13))
assert(7423007155473283614010.is_almost_prime(13))
assert(3108276166302017120182510.is_almost_prime(14))
assert(1393807661947063401736092760.is_almost_prime(17))
assert(32749388246772812069108696710.is_almost_prime(16))
assert(1421044357661885128003268103460.is_almost_prime(17))

assert(!is_almost_prime(503**72 * (2**64 + 1), 77))
assert(!is_almost_prime(503**76 * (2**64 + 1), 77))
assert(!is_almost_prime(503**77 * (2**64 + 1), 77))
assert(!is_almost_prime(503**78 * (2**64 + 1), 77))
assert(is_almost_prime(503**75 * (2**64 + 1), 77))

assert(!is_almost_prime(503**74 * (2**128 + 1), 77))
assert(!is_almost_prime(503**76 * (2**128 + 1), 77))
assert(!is_almost_prime(503**77 * (2**128 + 1), 77))
assert(!is_almost_prime(503**78 * (2**128 + 1), 77))
assert(is_almost_prime(503**75 * (2**128 + 1), 77))

assert(!is_almost_prime(3449**74 * 1e100.random_prime, 76))
assert(!is_almost_prime(3449**76 * 1e100.random_prime, 76))
assert(is_almost_prime(3449**75 * 1e100.random_prime, 76))

assert(
    %n[28, 16, 176, 4950, 8910, 1408, 346500, 277992, 7542080, 326656, 544320, 120400000, 145213440, 48549888, 4733575168, 536813568, 2149576704, 3057500160, 938539560960, 1358951178240, 36324805836800, 99956555776, 49212503949312, 118747221196800, 59461613912064, 13749193801728, 7526849672380416, 98516240758210560, 4969489493917696, 78673429816934400, 4467570822566903808, 1013309912383488000].map_kv{|k,v|
        v.is_almost_prime(k+3)
    }.all
)

assert_eq(
    %n[1, 3, 9, 43, 46, 47, 245, 1697, 109, 565, 3938, 3255, 30089, 18951, 2217].map_kv{|n,k| is_almost_prime(k**(n+1) + 1, n+1) },
    15.of(true)
)

assert_eq(
    %n[2, 3, 3, 43, 7, 41, 23, 643, 17, 557, 251, 13183, 1999, 10007, 107].map_kv{|n,k| is_almost_prime(k**(n+1) + 1, (n+1)) },
    15.of(true)
)

assert(is_almost_prime(33577**18 + 1, 18))
assert(!is_almost_prime((2**64 + 1) * 503**78, 77))
assert(is_almost_prime((2**64 + 1) * 503**78, 80))

say "** Test passed!"