783:
20:
1092:
158:
Although some integer sequences have definitions, there is no systematic way to define what it means for an integer sequence to be definable in the universe or in any absolute (model independent) sense.
90:
Alternatively, an integer sequence may be defined by a property which members of the sequence possess and other integers do not possess. For example, we can determine whether a given integer is a
247:. However, in any model that does possess such a definability map, some integer sequences in the model will not be definable relative to the model (Hamkins et al. 2013).
974:
174:. The transitivity of M implies that the integers and integer sequences inside M are actually integers and sequences of integers. An integer sequence is a
617:
964:
1057:
69:) is formed by starting with 0 and 1 and then adding any two consecutive terms to obtain the next one: an implicit description (sequence
522:
101:
76:
898:
908:
1072:
903:
663:
610:
1052:
1062:
954:
944:
278:
if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
1121:
1067:
969:
603:
458:
223:; for others, only some integer sequences are (Hamkins et al. 2013). There is no systematic way to define in
65:
by giving a relationship between its terms. For example, the sequence 0, 1, 1, 2, 3, 5, 8, 13, ... (the
1095:
1077:
517:
1116:
959:
542:
Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013), "Pointwise
Definable Models of Set Theory",
463:
949:
939:
929:
544:
204:, there are definable integer sequences that are not computable, such as sequences that encode the
453:
1044:
866:
489:
372:
296:
706:
653:
527:
913:
658:
377:
192:) in the language of set theory, with one free variable and no parameters, which is true in
1024:
861:
630:
336:
306:
8:
1004:
871:
504:
479:
387:
118:
934:
845:
830:
802:
782:
721:
571:
553:
468:
397:
1034:
835:
807:
761:
751:
731:
716:
484:
311:
275:
575:
1019:
840:
766:
756:
736:
563:
437:
427:
422:
392:
357:
347:
326:
321:
167:
66:
24:
797:
726:
362:
291:
1029:
1014:
1009:
688:
673:
432:
417:
412:
352:
316:
254:
contains all integer sequences, then the set of integer sequences definable in
235:. Similarly, the map from the set of formulas that define integer sequences in
171:
91:
1110:
994:
668:
176:
19:
999:
741:
683:
499:
494:
442:
407:
402:
367:
331:
746:
693:
447:
301:
205:
148:
144:
79:). The sequence 0, 3, 8, 15, ... is formed according to the formula
35:
589:
567:
595:
382:
28:
678:
473:
341:
140:
626:
152:
43:
558:
47:
96:
71:
239:
to the integer sequences they define is not definable in
975:
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ⋯ (inverses of primes)
965:
1 − 1 + 2 − 6 + 24 − 120 + ⋯ (alternating factorials)
111:
541:
286:
Integer sequences that have their own name include:
155:), and so not all integer sequences are computable.
139:> 0. The set of computable integer sequences is
227:itself the set of sequences definable relative to
1108:
104:), even though we do not have a formula for the
200:for all other integer sequences. In each such
611:
231:and that set may not even exist in some such
1058:Hypergeometric function of a matrix argument
274:A sequence of positive integers is called a
914:1 + 1/2 + 1/3 + ... (Riemann zeta function)
618:
604:
970:1 + 1/2 + 1/3 + 1/4 + ⋯ (harmonic series)
557:
523:On-Line Encyclopedia of Integer Sequences
122:if there exists an algorithm that, given
625:
18:
592:. Articles are freely available online.
196:for that integer sequence and false in
1109:
215:of ZFC, every sequence of integers in
143:. The set of all integer sequences is
599:
269:
53:An integer sequence may be specified
935:1 − 1 + 1 − 1 + ⋯ (Grandi's series)
13:
262:and be countable and countable in
112:Computable and definable sequences
14:
1133:
1053:Generalized hypergeometric series
583:
87:th term: an explicit definition.
1091:
1090:
1063:Lauricella hypergeometric series
781:
1073:Riemann's differential equation
1:
1068:Modular hypergeometric series
909:1/4 + 1/16 + 1/64 + 1/256 + ⋯
535:
459:Regular paperfolding sequence
184:if there exists some formula
83: − 1 for the
16:Ordered list of whole numbers
590:Journal of Integer Sequences
57:by giving a formula for its
7:
1078:Theta hypergeometric series
518:Constant-recursive sequence
511:
281:
211:For some transitive models
46:(i.e., an ordered list) of
10:
1138:
960:Infinite arithmetic series
904:1/2 + 1/4 + 1/8 + 1/16 + ⋯
899:1/2 − 1/4 + 1/8 − 1/16 + ⋯
1086:
1043:
987:
922:
891:
884:
854:
823:
816:
790:
779:
702:
646:
637:
545:Journal of Symbolic Logic
219:is definable relative to
373:Highly composite numbers
791:Properties of sequences
116:An integer sequence is
654:Arithmetic progression
528:List of OEIS sequences
464:Rudin–Shapiro sequence
378:Highly totient numbers
31:
1045:Hypergeometric series
659:Geometric progression
307:Binomial coefficients
243:and may not exist in
179:sequence relative to
153:that of the continuum
22:
1122:Arithmetic functions
1025:Trigonometric series
817:Properties of series
664:Harmonic progression
480:Superperfect numbers
388:Hyperperfect numbers
337:Even and odd numbers
208:of computable sets.
1005:Formal power series
568:10.2178/jsl.7801090
505:Wolstenholme number
490:Thue–Morse sequence
469:Semiperfect numbers
297:Baum–Sweet sequence
108:th perfect number.
803:Monotonic function
722:Fibonacci sequence
485:Triangular numbers
454:Recamán's sequence
398:Kolakoski sequence
312:Carmichael numbers
270:Complete sequences
67:Fibonacci sequence
32:
25:Fibonacci sequence
1117:Integer sequences
1104:
1103:
1035:Generating series
983:
982:
955:1 − 2 + 4 − 8 + ⋯
950:1 + 2 + 4 + 8 + ⋯
945:1 − 2 + 3 − 4 + ⋯
940:1 + 2 + 3 + 4 + ⋯
930:1 + 1 + 1 + 1 + ⋯
880:
879:
808:Periodic sequence
777:
776:
762:Triangular number
752:Pentagonal number
732:Heptagonal number
717:Complete sequence
639:Integer sequences
438:Practical numbers
428:Partition numbers
348:Fibonacci numbers
327:Deficient numbers
322:Composite numbers
276:complete sequence
27:on a building in
23:Beginning of the
1129:
1094:
1093:
1020:Dirichlet series
889:
888:
821:
820:
785:
757:Polygonal number
737:Hexagonal number
710:
644:
643:
620:
613:
606:
597:
596:
578:
561:
393:Juggler sequence
358:Figurate numbers
292:Abundant numbers
168:transitive model
162:Suppose the set
99:
74:
40:integer sequence
1137:
1136:
1132:
1131:
1130:
1128:
1127:
1126:
1107:
1106:
1105:
1100:
1082:
1039:
988:Kinds of series
979:
918:
885:Explicit series
876:
850:
812:
798:Cauchy sequence
786:
773:
727:Figurate number
704:
698:
689:Powers of three
633:
624:
586:
538:
514:
509:
433:Perfect numbers
423:Padovan numbers
418:Natural numbers
413:Motzkin numbers
363:Golomb sequence
317:Catalan numbers
284:
272:
134:
114:
95:
70:
17:
12:
11:
5:
1135:
1125:
1124:
1119:
1102:
1101:
1099:
1098:
1087:
1084:
1083:
1081:
1080:
1075:
1070:
1065:
1060:
1055:
1049:
1047:
1041:
1040:
1038:
1037:
1032:
1030:Fourier series
1027:
1022:
1017:
1015:Puiseux series
1012:
1010:Laurent series
1007:
1002:
997:
991:
989:
985:
984:
981:
980:
978:
977:
972:
967:
962:
957:
952:
947:
942:
937:
932:
926:
924:
920:
919:
917:
916:
911:
906:
901:
895:
893:
886:
882:
881:
878:
877:
875:
874:
869:
864:
858:
856:
852:
851:
849:
848:
843:
838:
833:
827:
825:
818:
814:
813:
811:
810:
805:
800:
794:
792:
788:
787:
780:
778:
775:
774:
772:
771:
770:
769:
759:
754:
749:
744:
739:
734:
729:
724:
719:
713:
711:
700:
699:
697:
696:
691:
686:
681:
676:
671:
666:
661:
656:
650:
648:
641:
635:
634:
623:
622:
615:
608:
600:
594:
593:
585:
584:External links
582:
581:
580:
552:(1): 139–156,
537:
534:
533:
532:
531:
530:
520:
513:
510:
508:
507:
502:
497:
492:
487:
482:
477:
471:
466:
461:
456:
451:
445:
440:
435:
430:
425:
420:
415:
410:
405:
400:
395:
390:
385:
380:
375:
370:
365:
360:
355:
353:Fibonacci word
350:
345:
339:
334:
329:
324:
319:
314:
309:
304:
299:
294:
288:
283:
280:
271:
268:
258:will exist in
172:ZFC set theory
130:
113:
110:
92:perfect number
15:
9:
6:
4:
3:
2:
1134:
1123:
1120:
1118:
1115:
1114:
1112:
1097:
1089:
1088:
1085:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1061:
1059:
1056:
1054:
1051:
1050:
1048:
1046:
1042:
1036:
1033:
1031:
1028:
1026:
1023:
1021:
1018:
1016:
1013:
1011:
1008:
1006:
1003:
1001:
998:
996:
995:Taylor series
993:
992:
990:
986:
976:
973:
971:
968:
966:
963:
961:
958:
956:
953:
951:
948:
946:
943:
941:
938:
936:
933:
931:
928:
927:
925:
921:
915:
912:
910:
907:
905:
902:
900:
897:
896:
894:
890:
887:
883:
873:
870:
868:
865:
863:
860:
859:
857:
853:
847:
844:
842:
839:
837:
834:
832:
829:
828:
826:
822:
819:
815:
809:
806:
804:
801:
799:
796:
795:
793:
789:
784:
768:
765:
764:
763:
760:
758:
755:
753:
750:
748:
745:
743:
740:
738:
735:
733:
730:
728:
725:
723:
720:
718:
715:
714:
712:
708:
701:
695:
692:
690:
687:
685:
684:Powers of two
682:
680:
677:
675:
672:
670:
669:Square number
667:
665:
662:
660:
657:
655:
652:
651:
649:
645:
642:
640:
636:
632:
628:
621:
616:
614:
609:
607:
602:
601:
598:
591:
588:
587:
577:
573:
569:
565:
560:
555:
551:
547:
546:
540:
539:
529:
526:
525:
524:
521:
519:
516:
515:
506:
503:
501:
500:Weird numbers
498:
496:
493:
491:
488:
486:
483:
481:
478:
475:
472:
470:
467:
465:
462:
460:
457:
455:
452:
449:
446:
444:
443:Prime numbers
441:
439:
436:
434:
431:
429:
426:
424:
421:
419:
416:
414:
411:
409:
408:Lucas numbers
406:
404:
403:Lucky numbers
401:
399:
396:
394:
391:
389:
386:
384:
381:
379:
376:
374:
371:
369:
368:Happy numbers
366:
364:
361:
359:
356:
354:
351:
349:
346:
343:
340:
338:
335:
333:
332:Euler numbers
330:
328:
325:
323:
320:
318:
315:
313:
310:
308:
305:
303:
300:
298:
295:
293:
290:
289:
287:
279:
277:
267:
265:
261:
257:
253:
248:
246:
242:
238:
234:
230:
226:
222:
218:
214:
209:
207:
203:
199:
195:
191:
187:
183:
182:
178:
173:
169:
165:
160:
156:
154:
150:
146:
142:
138:
133:
129:
126:, calculates
125:
121:
120:
109:
107:
103:
98:
93:
88:
86:
82:
78:
73:
68:
64:
60:
56:
51:
49:
45:
41:
37:
30:
26:
21:
1000:Power series
742:Lucas number
694:Powers of 10
674:Cubic number
638:
549:
543:
495:Ulam numbers
302:Bell numbers
285:
273:
263:
259:
255:
251:
249:
244:
240:
236:
232:
228:
224:
220:
216:
212:
210:
206:Turing jumps
201:
197:
193:
189:
185:
180:
175:
163:
161:
157:
136:
131:
127:
123:
117:
115:
105:
94:, (sequence
89:
84:
80:
62:
61:th term, or
58:
54:
52:
39:
33:
867:Conditional
855:Convergence
846:Telescoping
831:Alternating
747:Pell number
448:Pseudoprime
383:Home primes
149:cardinality
145:uncountable
36:mathematics
1111:Categories
892:Convergent
836:Convergent
536:References
135:, for all
119:computable
63:implicitly
55:explicitly
29:Gothenburg
923:Divergent
841:Divergent
703:Advanced
679:Factorial
627:Sequences
559:1105.4597
474:Semiprime
342:Factorial
177:definable
151:equal to
141:countable
1096:Category
862:Absolute
576:43689192
512:See also
282:Examples
48:integers
44:sequence
872:Uniform
476:numbers
450:numbers
344:numbers
100:in the
97:A000396
75:in the
72:A000045
824:Series
631:series
574:
147:(with
767:array
647:Basic
572:S2CID
554:arXiv
166:is a
42:is a
38:, an
707:list
629:and
102:OEIS
77:OEIS
564:doi
250:If
170:of
34:In
1113::
570:,
562:,
550:78
548:,
266:.
50:.
709:)
705:(
619:e
612:t
605:v
579:.
566::
556::
264:M
260:M
256:M
252:M
245:M
241:M
237:M
233:M
229:M
225:M
221:M
217:M
213:M
202:M
198:M
194:M
190:x
188:(
186:P
181:M
164:M
137:n
132:n
128:a
124:n
106:n
85:n
81:n
59:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.