A063131 Odd composite numbers which in base 2 contain their largest proper factor as a substring of digits.

55, 91, 215, 407, 493, 893, 1189, 1343, 1403, 1643, 1681, 1961, 3151, 3223, 3415, 4063, 4579, 7087, 7597, 7979, 8791, 9167, 10579, 11227, 13303, 13655, 14219, 15487, 16147, 22939, 23479, 24341, 25751, 26101, 27571, 28757, 30461, 30607

Offset: 1

Author

Robert G. Wilson v, Aug 08 2001

Keywords

• base
• nonn

Comments

The Pascal program checks to n=100000 in about a second on a 2GHz desktop, about three times as fast than the Mathematica program.

Links

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

Crossrefs

Cf. A062238, A063127.

Programs

Magma

[k:k in [3..31000 by 2] | not IsPrime(k) and IntegerToString(Seqint(Intseq(Max(Set(Divisors(k)) diff {k}),2))) in IntegerToString(Seqint(Intseq(k)),2)]; // Marius A. Burtea, Jan 29 2020

Mathematica

Do[ If[ !PrimeQ[ n ] && StringPosition[ ToString[ FromDigits[ IntegerDigits[ n, 2 ] ] ], ToString[ FromDigits[ IntegerDigits[ Divisors[ n ] [ [ -2 ] ], 2 ] ] ] ] != {}, Print[ n ] ], {n, 3, 500, 2} ]

Pascal

program A063131; var n,nn,lpd:longint; nstr,dstr:string; function prime(n:longint; var d:longint):boolean; var sq,i:longint; begin{PRIME} sq := round(sqrt(n)); for i := 2 to sq do if n mod i=0 then begin d := n div i; prime := false; exit; end; prime := true; end{PRIME}; begin{MAIN} for n := 3 to 100000 do if (n mod 2=1) and (not prime(n,lpd)) then begin nn := n; nstr := ''; repeat if nn mod 2=1 then nstr := '1'+nstr else nstr := '0'+nstr; nn := nn div 2; until nn=0; dstr := ''; repeat if lpd mod 2=1 then dstr := '1'+dstr else dstr := '0'+dstr; lpd := lpd div 2; until lpd=0; if pos(dstr,nstr)>0 then write(n:8); end; end.

Python

from sympy import divisors, isprime
def ok(n):
    if n < 4 or n&1 == 0 or isprime(n): return False
    return bin(divisors(n)[-2])[2:] in bin(n)[2:]
print([k for k in range(10**5) if ok(k)]) # Michael S. Branicky, Jul 29 2022

Extensions

Extended and edited by John W. Layman, Apr 06 2002